[USACO10FEB] Chocolate Eating

原题链接

很典型的二分答案题目。但是新颖点是他要输出每块巧克力在哪一天吃，很多人（包括我自己）就可能想当然的直接在累加的时候处理，如下：

    for (int i=1;i<=d;i++){
        sum/=2;
        while (sum<m){
            if (cnt>n) return false;
            sum+=a[cnt];
            b[cnt++]=i;
        }
    }

这么做本身没问题，但是会导致当最后一段sum>=m时会有相当一部分的bi没有存上值。修改如下：

bool check(ll m){
    ll sum=0,cnt=1;
    for (int i=1;i<=d;i++){
        sum/=2;
        while (sum<m){
            if (cnt>n) return false;
            sum+=a[cnt];
            b[cnt++]=i;
        }
    }
    if (cnt<=n)
        for (int i=cnt;i<=n;i++) b[i]=d;
    return true;
}

还有一点，由于我们实在check时对b数组进行处理，那么我们不一定保证最后一次执行check时一定会产生正确答案，所以我们要在找出对应的值时再执行一次check。

主要代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+5;
int a[N],b[N],d,n;
bool check(ll m){
    ll sum=0,cnt=1;
    for (int i=1;i<=d;i++){
        sum/=2;
        while (sum<m){
            if (cnt>n) return false;
            sum+=a[cnt];
            b[cnt++]=i;
        }
    }
    if (cnt<=n)
        for (int i=cnt;i<=n;i++) b[i]=d;
    return true;
}
int main(){
//    freopen("input2.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    std::ios::sync_with_stdio(false);
    cin>>n>>d;
    ll left=0,right=1;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        right+=a[i];
    }
    while (left+ll(1)<right){
        ll mid=(left+right)>>1;
        if (check(mid)) left=mid;
        else right=mid;
    }
    check(left);   //不要忘了额外执行一次
    cout<<left<<"\n";
    for (int i=1;i<=n;i++) 
        cout<<b[i]<<"\n";
    return 0;
}