【bzoj2016】[Usaco2010]Chocolate Eating

2014年10月21日1,8121

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

题解

二分+判定答案。。。

注意剩下的巧克力应该在最后一天吃掉

 

  • 王添民2015年1月6日 下午4:40 回复

    其实最后输出答案的时候不用判断
    在Judge里面,if(f)for(int i=now+1;i<=n;i++)a[now]=d;
    这句应该是 if(f) for (int i = now; i <= n; i++) a[now] = d;

    #1