题解 P2985 【[USACO10FEB]吃巧克力Chocolate Eating】

· · 题解

吐槽：这题难度应该是黄色吧

本题最大的坑点是记录食用日期 ( check函数不会太难写的 )

我个人的想法是先后求解两个子问题

  1. 先二分求出最不开心那天的最大开心值ans
  2. 再对ans重新check一遍以记录正确日期

原因：借鉴楼上：“因为这个程序会不管三七二十一地把所有的日期记录下来，不管可行与否”，所以只有当求出最优解ans后，check记录的日期才会是正解

#include<cstdio>
#define ll long long
//N<=50000 H_i<=1000000 累加起来将超过int范围
using namespace std;
const int N=50005;
inline ll read()
{
    ll s=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*f;
}
ll l,r,mid,ans;
ll n,d,a[N],day[N];
inline bool check(ll x)
{
    ll tot=0,sum=0;
    for(int i=1;i<=d;i++){
        sum=sum>>1;
        //">>1"表示除以2的一次方
        while(sum<x){
            sum+=a[++tot];
            if(tot>n) return false;
            //达不到检查值x便返回
            if(x&&x==ans) day[tot]=i;
            //if保证仅对ans记录日期
            //(当然可以去掉if，不过反复记录非正解很浪费)
        }
    }
    return true;
}
int main()
{
    n=read();d=read();
    for(int i=1;i<=n;i++)
    a[i]=read(),r+=a[i];
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    //二分最低开心值的区间
    printf("%lld\n",ans);
    check(ans);
    for(int i=1;i<=n;i++){
        if(day[i]) printf("%lld\n",day[i]);
        else printf("%lld\n",d);
        //最后一个小坑点：在最后一天要吃完剩下的全部巧克力
        //“剩下”即未标记过食用日期的巧克力
    }
    return 0;
}

评测结果：AC 68ms（不上不下的）