首页 > 代码库 > BZOJ 2016: [Usaco2010]Chocolate Eating
BZOJ 2016: [Usaco2010]Chocolate Eating
题目
2016: [Usaco2010]Chocolate Eating
Time Limit: 10 Sec Memory Limit: 162 MBDescription
贝西从大牛那里收到了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
Silver
题解
又是一道坑题，好吧，在输出的时候有点小细节QAQ WA了几次。这道题的思路是二分答案，然后判断正确性。
代码
1 /*Author:WNJXYK*/ 2 #include<cstdio> 3 using namespace std; 4 5 const int Maxn=50000; 6 int n,d; 7 long long cho[Maxn+10]; 8 9 inline bool check(long long x){10 long long sum=0,days=1;11 for (int i=1;i<=n;i++){12 sum+=cho[i];13 while(sum>=x && days<=d){14 sum/=2;15 days++;16 }17 if (days>d) return true;18 }19 return false;20 }21 22 inline void print(long long x){23 long long sum=0,days=1;24 for (int i=1;i<=n;i++){25 sum+=cho[i];26 printf("%d\n",days);27 while(sum>=x && days<d){28 sum/=2;29 days++;30 }31 }32 }33 34 int main(){35 scanf("%d%d",&n,&d);36 for (int i=1;i<=n;i++) scanf("%lld",&cho[i]);37 long long left=0,right=0,mid;38 for (int i=1;i<=n;i++) right+=cho[i];39 while(left<=right){40 mid=(left+right)/2;41 if (check(mid)==false){42 right=mid-1;43 }else{44 left=mid+1;45 }46 }47 printf("%lld\n",left-1);48 print(left-1);49 return 0;50 }
BZOJ 2016: [Usaco2010]Chocolate Eating
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。