题目描述
带上的包裹必须在 D 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天,我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
输入:weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出:15
解释:
船舶最低载重 15 就能够在 5 天内送达所有包裹,如下所示:
请在这里输入引用内容
第 1 天:1, 2, 3, 4, 5
第 2 天:6, 7
第 3 天:8
第 4 天:9
第 5 天:10
最低运载能力肯定是大于每个包裹的重量的,所以遍历找到最大值。
然后开始计算,以此值作为答案,需要的天数是否会超过需要的天数,超过时加大运载能力,小于等于时输出。
class Solution { public: int shipWithinDays(vector<int>& weights, int D) { int v=0; for(auto i:weights) if(i>v) v=i; while(true){ int temp=v,count=1; for(int i:weights){ if(temp-i<0){ count++; if(count>D) break; temp=v; } temp-=i; } if(count<=D) break;//小于也可以,说明已绰绰有余 v++; } return v; } };
优化:
每个包裹的重量<最低运载能力<包裹总重量
即,包裹重量最大值<最低运载能力<包裹总重量
然后二分法,天数大于时向右看,天数向左时向左看,找到分界点。
class Solution { public: int shipWithinDays(vector<int>& weights, int D) { int left=0,right=0; for(auto i:weights){ if(i>left) left=i; right+=i; } while(left<right){ int mid=(right-left)/2+left; if(cancarry(weights,D,mid)>D) left=mid+1; else right=mid; } return left; } int cancarry(vector<int>& weights,int D, int v){ int count=1,temp=v; for(int i:weights){ if(temp-i<0){ count++; temp=v; } temp-=i; } return count; } };