P1182-数列分段 - 从萌新到萌新的成长历程

题目传送门

题目思路

直接二分搜答案，输入的时候记录和，二分找就行了。

值得注意的是需要在最后一个元素后将分割数处理一下，同时记录各项值的更新

AC代码

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    long long sum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    long long l = 0;
    long long r = sum;
    long long ans = sum;
    while (l < r)
    {
        long long mid = (l + r) / 2;
        long long fsum = 0;
        long long fans = 0;
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            if (fsum + a[i] <= mid)
                fsum += a[i];
            else
            {
                if (fsum > fans)
                    fans = fsum;
                fsum = a[i];
                cnt++;
            }
        }
        if (fsum <= mid)
        {
            if (fsum > fans)
                fans = fsum;
            cnt++;
        }
        if (cnt < m)
        {
            r = mid;
        }
        else if (cnt > m)
        {
            l = mid + 1;
        }
        else if (cnt == m)
        {
            r = mid;
            if (fans < ans)
                ans = fans;
        }
    }
    cout << ans << endl;
    return 0;
}