问题 5322 --吃糖-训练套题T4T4

5322: 吃糖-训练套题T4T4

时间限制: 1 Sec  内存限制: 128 MB
提交: 43  解决: 7
[提交][状态][讨论版][命题人:]

题目描述

4. [吃糖ceafing.pas/ c/cpp]

【问题描述】

BessieN(1N50,000)颗糖果,编号1..N,但她不打算马上吃光,而是计算在接下来的D(1D50,000)天按糖果编号从小到大逐天吃,当然,Bessie以一天连续吃多颗糖果,也可以不吃,但不能跳着糖果来吃,要按糖果顺序吃。

  吃了糖果iBessie's的能量值会增加H_i(1H_i1000,000)Bessie都是在白天吃糖果,然后晚上睡觉,第二天醒来,她的能量值会变成前一天的能量值的一半(向下取整)Bessie's的能量值会累加。请你决定第i颗糖果应该是第几天吃,才能使得Bessie在这D个晚上里,能量值最小的那个晚上(假设是第x个晚上),第x个晚上的能量值最大?输出该值,并且输出第1(1iN)颗糖果是Bessie第几天吃掉的。

    例如:有5个糖果,能量值分别是:(104013227)

    Bessie按以下方式吃糖果,将会得到最优值:

    第几天  醒来时能量值   吃了糖果后能量值   晚上睡觉能量值

    1                  0               10+40            50

    2           25                -----             25

    3           12               13               25

    4           12               22               34

    5           17               7                24

    可以看出,第1天吃了糖果1、糖果2,第2天不吃糖果,第3天吃了糖果3,第4天吃了糖果4,第5天吃了糖果5。那么在这5个晚上,能量值最低的是第5个晚上,能量值是24,所以输出24。然后你还要输出第1(1iN)颗糖果是Bessie第几天吃掉的。

【输入数据】

1行:两个整数:ND

2..N+1行:每行一个整数H_i

【输出数据】

l行:一个整数,在这D个晚上里,能量值最小的那个晚上(假设是第X个晚上),第x个晚上的能量值最大可以是多少?

  2..N+1行:每行一个整数,第i行表示第i颗糖果是第几天被吃的。

【输入样例】

5 5

  10

  40

  13

  22

  7

【输出样例】

24

  1

  1

  3

  4

  5

 

提示


ceafing



    算法分析:



    本题可以用二分答案去解决。当我们知道答案后,贪心地去吃糖果,从左往右扫描糖



果,如果当前的能量没有达到答案,那么必须把当前的那颗糖果吃掉,如果当前的能量已



经达到了答案,那么当天没有必要再吃当前的那颗糖果,留着第二天吃更好。如此扫描下



去,看最后能维持的天数是否达到题目给出的天数d,如果达到,则是可行的,否则是不可行。时间复杂度是O(NlogN)

来源

 

[提交][状态]