链接
https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/
耗时
解题:62 min
题解:30 min
题意
传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天,我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
提示:
- 1 <= D <= weights.length <= 50000
- 1 <= weights[i] <= 500
思路
二分答案。将所有重量的和作为上边界,最大的重量作为下边界。
对于当前的 载重能力,贪心的判断最少需要多少天才能将传送带上的所有包裹送达。如果需要的天数小于等于 D,说明当前的载重能力可以,则将中间值赋给下边界,如果大于 D,说明不可以,将中间值赋给上边界。
时间复杂度:
O
(
l
o
g
(
t
−
s
)
)
O(log(t-s))
O(log(t−s))
AC代码
class Solution {
private:
vector<int> weights;
int D;
public:
bool check(int capacity) {
int day_cnt = 0, curr_wei = 0;
for(auto weight : weights) {
if(curr_wei + weight > capacity) {
day_cnt++;
curr_wei = 0;
}
if(day_cnt > D) return false;
curr_wei += weight;
}
day_cnt++;
return day_cnt <= D;
}
int shipWithinDays(vector<int>& weights, int D) {
this->weights = weights;
this->D = D;
int sum_wei = accumulate(weights.begin(), weights.end(), 0);
int max_wei = *max_element(weights.begin(), weights.end());
int s = max_wei, t = sum_wei;
while(s < t) {
int m = s + ((t-s)>>1);
if(check(m)) t = m;
else s = m+1;
}
return s;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)