[USACO 2010 Feb S]Chocolate Eating

二分的对象是幸福感

#include <iostream>

using namespace std;

typedef long long LL;//啥也不说了，直接全部long long
const int N = 1e6 + 10;

int n, d;
LL level;//题目要求的幸福感
LL a[N], c[N];//a用来存巧克力  c用来表示每一块巧克力哪一天吃

bool check(LL x)
{
    LL sum = 0, t = 0;//sum表示每一天的幸福感 t表示吃掉的巧克力数量
    for(int i = 1; i <= d; i ++)
    {
        while(sum < x)//当这一天的幸福感不够 就吃巧克力 
        {
            sum += a[++ t];
            if(t > n) return false;//吃掉的巧克力数量大于现有的巧克力数量
            if(x == level) c[t] = i;//如果当前的x就是最终的level，记录一下每块巧克力是哪天吃的
        }
        sum /= 2;//每天晚上幸福感减半
    }
    
    return true;
}

int main()
{
    cin >> n >> d;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    
    LL l = 0, r = 1e11;//幸福感最大5e10
    while(l < r)//这里想找最大的幸福感，明显是找右边界，直接二分查找右边界模板
    {
        LL mid = l + r + 1 >> 1;
        if(!check(mid)) r = mid - 1;//如果幸福感太大了，不能达到那我们就需要把右边界往左移
        else l = mid;//辛福感有点小，可以达到，左边界往右移
    }
    
    level = l;
    check(level);//这里的check是记录一下每块巧克力在哪天吃
    cout << level << endl;
    for(int i = 1; i <= n; i ++)
    {
        if(c[i]) cout << c[i] << endl;
        //可能存在当前这一天即使不用吃任何巧克力幸福感也可以达到当前二分出来的level，也就是说会有巧克力没吃完的情况， 因为题目要求所有巧克力都要吃完，所以我们要在最后一天把所有剩下巧克力吃完
        else cout << d << endl;
    }
        
    return 0;
}