题解 | #Shopee的零食柜#

虽然数据的通过情况是4 / 7，但我怀疑是数据的问题，如果是代码的问题，那么请大佬们一定要为我指出，感谢！

题意：一个长度为n的序列，最多“切割（即连续地划分）”成m组，对这些组分别求组内元素和，问这些组内元素和的最小值是多少。

思路：二分答案

代码：

#include <iostream>
using namespace std;

const int N = 1000010;
int n, m;
int a[N];

bool check (int x) { // 判断答案为 x 时可不可以
    int sum = 0, cnt = 0;
    for (int i = 1; i <= n; ++ i) { // 简单的划分过程
        if (sum + a[i] <= x) {
            sum += a[i];
        } else {
            ++ cnt;
            sum = a[i];
        }
    }
    ++ cnt;
    return cnt <= m;
}

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);

    int l = 0, r = 0;
    for (int i = 1; i <= n; ++ i) { // 确定二分的上下界
        l = max(l, a[i]);
        r += a[i];
    }
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid) == true) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    printf("%d", l);
    return 0;
}