【USACO FEB 2010 SILVER】吃巧克力
时间限制: 1 Sec 内存限制: 128 MB
题目描述
Bessie拿到了N (1 <= N <= 50,000)块巧克力。她决定想个办法吃掉这些巧克力，使得它在吃巧克力的这段时间里，最不开心的一天尽可能的开心。并且一共吃D (1 <= D <= 50,000)天。
每块巧克力有一个开心值H_i (1 <= H_i <= 1,000,000)，当某天你吃下那块巧克力时，你将获得那块巧克力的开心值。每一天的开心值是所有当天吃掉的巧克力的总开心值之和。每天晚上Bessie睡觉之后，它的开心值会减半。也就是说，比如昨天Bessie的开心值为50，那么今天早上我一醒来我就会有25点的开心值，舍去小数点后数字。另外，Bessie还有一个怪癖，她喜欢按照巧克力本来的排列顺序吃。
Bessie第一天的开心值为0，求一个每天吃巧克力的方案，使得Bessie最不开心的一天尽可能的开心。
输入
第1行：2个整数N和D
接下来N行，每行1个整数H_i
输出
第1行：1个整数，表示最不开心的一天的最大开心值
接下来N行，每行一个整数，表示第i块巧克力是第几天吃的
样例输入
5 5
10
40
13
22
7
样例输出
24
1
1
3
4
5
就是二分
一开始传参数时mid写的int类型，LL转换为int也没警告，然后一直乱wa对拍了几万组极限数据也没找到问题。。
以后注意
#include<cstdio>
#include<climits>
#define LL long long
LL cbs[50100];
int tag[50100];
int n,d;
bool tryf(LL mid){
bool flag=true;
int at=1;
LL sum=0;
for(int i=1;i<=d;i++){
if(sum)sum=sum>>1;
while(sum<mid)tag[at]=i,sum+=cbs[at++];
if(at>n+1){flag=false;break;}
}
for(;at<=n;at++)tag[at]=d;
return flag;
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out1.txt","w",stdout);
LL l=0,r=0,mid;
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++)
scanf("%lld",&cbs[i]),r+=cbs[i];
cbs[n+1]=10LL*INT_MAX;
LL ans;
while(l<r){
mid=(l+r+1)>>1;
if(tryf(mid))ans=mid,l=mid;
else r=mid-1;
}
tryf(ans);
printf("%lld
",ans);
bool f=false;
for(int i=1;i<=n;i++){
if(tag[i]==d)f=true;
if(f)printf("%d
",d);
else printf("%d
",tag[i]);
}
}