二分+贪心
观察ans具有单调性,同时判断是否可以分割采用贪心算法,贪心的证明可以使用最优解等于贪心解。
ref
C++ 代码
class Solution {
public:
int splitArray(vector<int>& nums, int k) {
int sum = 0;
for(int num : nums) sum += num;
int l = 0, r = sum;
while(l<r) {
int mid = l+r>>1;
if(check(nums, mid, k))r=mid;
else l = mid+1;
}
return r;
}
bool check(vector<int>& nums, int t, int k) {
int seg = 0;
for(int i=0, sum=0; i<nums.size(); ++i) {
if(nums[i] > t)return false;
if(sum + nums[i] <= t)sum += nums[i];
else {
seg++;
sum = nums[i];
}
if(seg == k)return false;
}
return true;
}
};