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

1、显然最小幸福度范围是0~5e10，二分找出满足check(int x)条件的最大x即可。
2、check(int x)函数，用sum表示当天的幸福度，遍历每一天，确保每一天的幸福度都达到x即可
3、如果sum<x则表明当天幸福度不够，需要吃掉一个巧克力，sum+=h[i]直到sum>=x
4、每吃掉一个巧克力h[idx]，用a[idx]记录下第idx块巧克力在第几天被吃掉
5、如果顺利遍历完所有天数，则return true
6、如果巧克力已经吃光了，但是还有天数不满足sum>=x，则return false

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+10;
int h[N],a[N];//h[N]保存每块巧克力的幸福度,a[N]保存每块巧克力在第几天被吃
int n,d;
bool check(int x)
{
    int idx=0;
    int sum=0;//当天结束时的幸福度
    for(int i=1;i<=d;i++)//遍历每一天，确保每一天的幸福度都>=x
    {
        while(sum<x)//当天的幸福度小于x
        {
            if(idx==n) return false;//巧克力已经吃光了，但还有天数幸福度没有达到x
            sum+=h[++idx];//按顺序吃掉巧克力
            a[idx]=i;//记录第idx块巧克力第i天被吃
        }
        sum/=2;//下一天幸福度要减半
    }
    while(idx<n) a[++idx]=d;//剩余巧克力都在最后一天被吃，确保每一块巧克力都被吃掉
    return true;
}
signed main()
{
    cin>>n>>d;
    for(int i=1;i<=n;i++) cin>>h[i];
    int l=0,r=5e10;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    check(l);//存在一种特殊情况,二分到最后只剩下两个元素L和R,即R比L大1，
    //L满足而R不满足,二分循环内mid=l+r+1>>1会等于R,然后check(R),不满足更新右边界
    //更新完右边界后,跳出循环,即跳出循环前最后一次是check(R)
    //此时a[N]中储存的是幸福度为R的情况下每块巧克力在第几天被吃
    //所以二分后要进行一次check(L);
    cout<<l<<endl;
    for(int i=1;i<=n;i++) cout<<a[i]<<endl;
}