410 分割数组的最大值
思路
class Solution {
public:
int f(vector<int>& nums, int x){
int cnt = 0;
int i = 0;
while(i < nums.size()){
int sum = x;
while(i < nums.size()){
if(sum >= nums[i]){
sum -= nums[i];
i++;
}else{
break;
}
}
cnt++;
}
return cnt;
}
int splitArray(vector<int>& nums, int k) {
int left = 0, right = 0;
for(int num : nums){
left = max(left, num);
right += num;
}
while(left <= right){
int mid = left + (right - left) / 2;
if(f(nums, mid) == k){
right = mid - 1;
}else if(f(nums, mid) < k){
right = mid - 1;
}else if(f(nums, mid) > k){
left = mid + 1;
}
}
return left;
}
};