题解 | #[USACO 2010 Feb S]Chocolate Eating#

存在最后的任务完成后，巧克力仍未分配完的情况

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int a[N];
void solve()
{
    int n, d;
    cin >> n >> d;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    auto check = [&](int x) -> bool
    {
        int l = 0, pre = 0, day = 0;
        while (day < d)
        {
            int now = pre;
            while (l < n && now < x)
            {
                now += a[l];
                l++;
            }
            if (now < x)
            {
                return false;
            }
            pre = now / 2;
            day++;
        }
        return true;
    };
    auto check1 = [&](int x) -> void
    {
        int l = 0, pre = 0, day = 0;
        while (day < d)
        {
            int now = pre;
            while (l < n && now < x)
            {
                cout<<day+1<<'\n';
                now += a[l];
                l++;
            }
            pre = now / 2;
            day++;
        }
        while(l<n)
        {
            cout<<day-1<<'\n';
        }
    };
    int l = 0, r = 1e18, mid;
    while (l + 1 != r)
    {
        mid = l + r >> 1;
        if (check(mid))
        {
            l = mid;
        }
        else
        {
            r = mid;
        }
    }
    cout << l << '\n';
    check1(l);
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}