P2985 [USACO10FEB]吃巧克力Chocolate Eating

admin

https://www.luogu.org/problemnew/show/P2985

题目描述
Bessie has received N (1 <= N <= 50,000) chocolates from the bulls, but doesn't want to eat them too quickly, so she wants to plan out her chocolate eating schedule for the next D (1 <= D <= 50,000) days in order to maximize her minimum happiness level over the set of those days.

Bessie's happiness level is an integer that starts at 0 and halves (rounding down if necessary) over night as she sleeps. However, when she eats chocolate i, her happiness level increases by integer H_i (1 <= H_i <= 1,000,000). If she eats chocolates on a day, her happiness for that day is considered the happiness level after she eats the chocolates. Bessie insists that she eat the chocolates in the order that she received them.

If more than one optimal solution exists, print any one of them.

Consider a sequence of 5 chocolates to be eaten over a period of 5 days; they respectively bring happiness (10, 40, 13, 22, 7).

If Bessie eats the first chocolate (10 happiness) on the first day and then waits to eat the others, her happiness level is 10 after the first day.

Here is the complete schedule which turns out to maximize her minimum happiness:

Day Wakeup happiness Happiness from eating Bedtime happiness 1 0 10+40 50

2 25 --- 25

3 12 13 25

4 12 22 34

5 17 7 24

The minimum bedtime happiness is 24, which turns out to be the best Bessie can do.

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最不开心的一天尽可能的开心。

输入输出格式
输入格式：
* Line 1: Two space separated integers: N and D

* Lines 2..N+1: Line i+1 contains a single integer: H_i

输出格式：
* Line 1: A single integer, the highest Bessie's minimum happiness can be over the next D days

* Lines 2..N+1: Line i+1 contains an integer that is the day on which Bessie eats chocolate i

输入输出样例
输入样例#1：
5 5
10
40
13
22
7
输出样例#1：
24
1
1
3
4
5

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. long long n,m,a[51000],zuo=0,you=0;
    
14. bool check(long long x)
    
15. {
    
16.         long long last=1,all=0;
    
17.         for(int i=1;i<=m;i++)
    
18.         {
    
19.                 while(x>all)
    
20.                 {
    
21.                         if(last==n+1)
    
22.                                 return false;
    
23.                         all+=a[last],last++;
    
24.                 }
    
25.                 all=all>>1;
    
26.         }
    
27.         return true;
    
28. }
    
29. int main()
    
30. {
    
31.         scanf("%lld%lld",&n,&m);
    
32.         for(int i=1;i<=n;i++)
    
33.                 scanf("%lld",&a[i]),you+=a[i];
    
34.         while(zuo<you)
    
35.         {
    
36.                 long long mid=(zuo+you+1)>>1;
    
37.                 if(check(mid)) zuo=mid;
    
38.                 else you=mid-1;
    
39.         }
    
40.         printf("%lld\n",zuo);
    
41.         long long last=1,all=0;
    
42.         for(int i=1;i<=m;i++)
    
43.         {
    
44.                 while(zuo>all)
    
45.                 {
    
46.                         all+=a[last],last++;
    
47.                         printf("%d\n",i);
    
48.                 }
    
49.                 all=all>>1;
    
50.         }
    
51.         for(int i=last;i<=n;i++)
    
52.                 printf("%lld\n",m);
    
53.         return 0;
    
54. }

复制代码