Skip to content

Instantly share code, notes, and snippets.

@fpdjsns
Last active March 22, 2019 06:59
Show Gist options
  • Save fpdjsns/cf33ccdf8aaf1ebe5f5438136eaae618 to your computer and use it in GitHub Desktop.
Save fpdjsns/cf33ccdf8aaf1ebe5f5438136eaae618 to your computer and use it in GitHub Desktop.
[leetcode] 1014. Capacity To Ship Packages Within D Days : https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
class Solution {
public:
int shipWithinDays(vector<int>& weights, int D) {
// find minimum weights can Answer
int l = 0;
int r = 0;
for(int i=0;i<weights.size();i++){
int nowWeight = weights[i];
l = max(l, nowWeight);
r += nowWeight;
}
int answer = 0;
while(l < r){
int maxSum = (l + r) / 2;
if(getDays(weights, maxSum) <= D) {// possible
r = maxSum;
}
else // impossible
l = maxSum + 1;
}
return r;
}
int getDays(vector<int> weights, int max){
int subSum = 0, day = 1;
for(int i=0;i<weights.size();i++){
int nowWeight = weights[i];
int nextSubSum = subSum + nowWeight;
if(max < nextSubSum ){ // impossible
day++;
subSum = nowWeight;
}else{
subSum = nextSubSum;
}
}
return day;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment