题意梳理
- 有 N 块巧克力，必须按顺序吃，一共 D 天。
- 幸福值初始cur=0；每晚睡觉后，幸福值向下取整减半。
- 某天吃若干巧克力：吃完巧克力后的幸福值，就是当天的幸福值。
- 目标：最大化D 天中每天睡前幸福值的最小值（最大化最小值，经典二分答案模型）。
- 输出：最大的最低幸福值；输出每一块巧克力在哪一天吃掉。
注意：数据范围很大，所以总和可以很大，要用long long防止溢出。
核心思想：二分答案
“最大化最小值” 标准套路：二分判定答案 mid：
check(x)函数：判断是否存在吃巧克力方案，保证每一天结束时幸福值都≥x，并且全部巧克力在 D 天内按顺序吃完。
如果check(x)=true：说明可以做到每天最低至少 x，尝试找更大，记录方案，二分右边界：l=mid+1。
如果check(x)=false：做不到，只能往小找：r=mid‑1。
二分范围：l=0，r=text所有巧克力幸福总和。
check函数完整解析
boolcheck(longlongx){longlongcur=0,s=0;//cur：当前幸福；s：已经吃掉的巧克力块数for(inti=1;i<=d;i++)//枚举第i天{cur/=2;//睡一觉，前一天晚上幸福减半，来到新一天起床//只要今天结束幸福还达不到x，就继续吃巧克力（按顺序）while(cur<x&&s<n){s++;cur+=a[s];b[s]=i;//记录第s块巧克力是第i天吃}if(cur<x)//今天吃完所有剩下巧克力依旧达不到x → x不可行{returnfalse;}}//循环走完D天，剩下没吃完的巧克力，全部丢在最后一天d吃for(inti=s+1;i<=n;i++){b[i]=d;}returntrue;}完整AC代码
#include<bits/stdc++.h>usingnamespacestd;intn,d;inta[50010],b[50010],c[50010];// check(x): 是否可以保证D天，每天结束幸福>=xboolcheck(longlongx){longlongcur=0;ints=0;//s:已经吃掉的巧克力数目for(inti=1;i<=d;i++){cur/=2;//睡一晚，幸福减半，新一天开始//当前幸福不足x，继续吃巧克力while(cur<x&&s<n){s++;cur+=a[s];b[s]=i;}if(cur<x)returnfalse;//今天无论如何达不到x}//D天走完，剩下全部放最后一天for(inti=s+1;i<=n;i++){b[i]=d;}returntrue;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n>>d;longlongsum=0;for(inti=1;i<=n;i++){cin>>a[i];sum+=a[i];}longlongl=0,r=sum,ans=0;while(l<=r){longlongmid=(l+r)/2;if(check(mid)){ans=mid;copy(begin(b),end(b),begin(c));l=mid+1;}else{r=mid-1;}}cout<<ans<<'\n';for(inti=1;i<=n;i++){cout<<c[i]<<'\n';}return0;}
