题目
2016: [Usaco2010]Chocolate Eating
Time Limit: 10 Sec Memory Limit: 162 MB
Description
贝西从大牛那里收到了N块巧克力。她不想把它们马上吃完,而是打算制定一个计划,
使得在接下来的D天里,她能够尽量地快乐。贝西的快乐指数可以用一个整数来衡量,一开始的时候是0,当她每天晚上睡觉的时候,快乐指数会减半(奇数时向下取整)。贝西把她的巧克力按照收到的时间排序,并坚持按照这个顺序来吃巧克力。当她吃掉第i块巧克力的时候,她的快乐指数会增加Hj。每天可以吃任意多块巧克力,如何帮助贝西合理安排,使得D天内她的最小快乐指数最大呢?
举个例子:假设一共有五块巧克力,贝西打算在五天时间内将它们吃完,每块巧克力提
供的快乐指数分别为10,40,13,22,7。则最好的方案如F:
天数 |
起床时快乐指数 |
食用的巧克力 |
就寝时快乐指数 |
1 |
0 |
10+ 40 |
50 |
五天内的最小快乐指数为24,这是所有吃法中的最大值。
Input
第一行:两个用空格分开的整数:N和D,1≤N.D≤50000
第二行到第N+1行:第1+1行表示第i块巧克力提供的快乐指数Hj,1≤Hi≤1000000
Output
第一行:单个整数,表示贝西在接下来D天内的最小快乐指数的最大值
第二行到第N+1:在第i+l行有一个整数,代表贝西应该在哪一天吃掉第i块巧克力。
如果有多种吃法,则输出按照词典序排序后最靠后的方案
Sample Input
55
10
40
13
22
7
10
40
13
22
7
Sample Output
24
1
1
3
4
5
1
1
3
4
5
HINT
Source
题解
又是一道坑题,好吧,在输出的时候有点小细节QAQ WA了几次。这道题的思路是二分答案,然后判断正确性。
代码
/*Author:WNJXYK*/
#include<cstdio>
using namespace std; const int Maxn=;
int n,d;
long long cho[Maxn+]; inline bool check(long long x){
long long sum=,days=;
for (int i=;i<=n;i++){
sum+=cho[i];
while(sum>=x && days<=d){
sum/=;
days++;
}
if (days>d) return true;
}
return false;
} inline void print(long long x){
long long sum=,days=;
for (int i=;i<=n;i++){
sum+=cho[i];
printf("%d\n",days);
while(sum>=x && days<d){
sum/=;
days++;
}
}
} int main(){
scanf("%d%d",&n,&d);
for (int i=;i<=n;i++) scanf("%lld",&cho[i]);
long long left=,right=,mid;
for (int i=;i<=n;i++) right+=cho[i];
while(left<=right){
mid=(left+right)/;
if (check(mid)==false){
right=mid-;
}else{
left=mid+;
}
}
printf("%lld\n",left-);
print(left-);
return ;
}