首页 > 代码库 > BZOJ 2016: [Usaco2010]Chocolate Eating

BZOJ 2016: [Usaco2010]Chocolate Eating

题目

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
    2
    3
    4
    5

    0
    25
    12
    12
    17

    10+ 40
 
    13
    22
    7

    50
    25
    25
    34
    24

 

 

 

 

五天内的最小快乐指数为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

Sample Output

24
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 }
View Code

 

BZOJ 2016: [Usaco2010]Chocolate Eating