推 Rushia: 大師 02/22 09:08
推 pandix: 大師 02/22 10:37
推 idiont: 大師 02/22 13:50
之前都用JPTT發廢文每篇都只值1P，來試試看用電腦發可以賺多少==
1011. Capacity To Ship Packages Within D Days
傳輸帶有n個包裹，每個重量<=500，給你一艘載重x的船，
每天照順序載走一些包裹且其總重<=x，問d天之內載完的最小船載重x多少?
1 <= d <= n <= 50000
然後就想到對答案二分搜了
C++ code:
class Solution {
public:
int shipWithinDays(vector<int>& weights, int days) {
int ws = weights.size();
int l = *max_element(weights.begin(), weights.end()), r = 25000000;
int d = 0, sum = 0;
while(l <= r){
int mid = l + (r - l)/2;
d = 0;
for(int i=0; i<ws; i++){
sum += weights[i];
if(sum > mid){sum = weights[i]; d++;}
else if(sum == mid){sum = 0; d++;}
}
if(sum){sum = 0; d++;}
if(d <= days) r = mid - 1;
else if(d > days) l = mid + 1;
}
return l;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.3.144.80 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1677027282.A.ED0.html