题解

#include <bits/stdc++.h>
using namespace std;
int arr[100000];
bool fsb(int max_sum, int n, int m) {  //判断是否满足每段和的最大值不超过max_sum的条件
    int segs = 1;
    int curr_sum = 0;
    for (int i = 0; i < n; ++i) {
        if (curr_sum + arr[i] > max_sum){  //如果加上当前数超过了max_sum
            segs++;
            curr_sum = arr[i];  //重新开始计算当前段的和
    	}
        else
            curr_sum += arr[i];
    }
    return segs <= m;
};
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    int left = *max_element(arr, arr + n);  //最小可能的每段和最大值
    int right = 0;
    for (int i = 0; i < n; ++i)
        right += arr[i];
    while (left < right) { //二分查找
        int mid = left + (right - left) / 2;
        if (fsb(mid, n, m))  //如果满足条件，缩小右边界
            right = mid;
        else
            left = mid + 1;
    }
    cout << left;
    return 0;
}