C++17 实现数组划分最小最大子数组和

给定一个包含 n 个正整数的数组 a。您的任务是将数组划分为 k 个子数组，以便子数组中的和的最大值尽可能小。

输入格式

第一行包含两个整数 n 和 k，表示数组的大小和需要划分的子数组的数量。

下一行包含 n 个整数

输出格式

一个整数，最大部分和的最小值

样例

输入样例

5 3
2 4 7 3 5

输出样例

8

C++17 实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool check(vector<int>& nums, int k, int target) {
int count = 0;
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
if (sum >= target) {
count++;
sum = 0;
}
}
return count >= k;
}
int splitArray(vector<int>& nums, int k) {
int left = *max_element(nums.begin(), nums.end());
int right = accumulate(nums.begin(), nums.end(), 0);
while (left &lt; right) {
    int mid = left + (right - left) / 2;
    if (check(nums, k, mid)) {
        right = mid;
    } else {
        left = mid + 1;
    }
}
return left;

}
int main() {
int n, k;
cin >> n >> k;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
int ans = splitArray(nums, k);
cout << ans << endl;
return 0;
}