[leetcode] 1011. Capacity To Ship Packages Within D Days

[leetcode] 1011. Capacity To Ship Packages Within D Days

Description

A conveyor belt has packages that must be shipped from one port to another within D days.

The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.

Example 1:

Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5Output: 15Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:1st day: 1, 2, 3, 4, 52nd day: 6, 73rd day: 84th day: 95th day: 10Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:

Input: weights = [3,2,2,4,1,4], D = 3Output: 6Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:1st day: 3, 22nd day: 2, 43rd day: 1, 4

Example 3:

Input: weights = [1,2,3,1,1], D = 4Output: 3Explanation: 1st day: 12nd day: 23rd day: 34th day: 1, 1

Constraints:

1 <= D <= weights.length <= 50000.1 <= weights[i] <= 500.

分析

题目的意思是：给定一个数组，分为D组，每个子数组的最大值在所有可能的分组情况下最小。有点拗口，就是有很多种分组情况，但是要求这种分组情况中，子数组的最大值在所有组合情况下最小。 这道题用二分法，当然我现在不会啦，首先是求出数组的最大值和求和，然后在这两个数之间用二分法找到这个满足条件的最大值了，二分的条件就是判断天数是否符合要求，如果小于规定的天数D，说明分得太少了，可以分得组更多一点，也就说明最大值可以更小一点；如果大于规定的天数，说明分得太多了，可以分得更少一点，也就说明最大值可以更大一点啦。理解了这个就能够理解而分法了哈。

代码

class Solution: def shipWithinDays(self, weights: List[int], D: int) -> int: def check_day(capacity): day=0 t=0 for i in range(len(weights)): t+=weights[i] if(t>capacity): day+=1 t=weights[i] return day n=len(weights) low,high=max(weights),sum(weights) while(low<=high): middle=low+(high-low)//2 if(check_day(middle)

参考文献

​​[LeetCode] [Python] Binary Search Solution, similar problems attached.​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。