P1182 数列分段 Section II

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[10000007];
bool check(int x)
{
    int sum = 0, cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        sum += a[i];
        if(a[i] > x)return false;
        if (sum > x)
        {
            cnt++;
            sum = a[i];
        }
    }
    cnt++;
    return cnt > m;
}
int find(int l, int r)
{
    if (l + 1 >= r)
        return r;
    int mid = (l + r) / 2;
    if (check(mid))
        return find(mid, r);
    else
        return find(l, mid);
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cout << find(1, 1e9) << endl;
    system("pause");
    return 0;
}