3607: 吃糖-训练套题T4T4

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

【问题描述】

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

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

    例如：有5个糖果，能量值分别是：(10，40，13，22，7)。

    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(1≤i≤N)颗糖果是Bessie第几天吃掉的。

【输入数据】

第1行：两个整数：N和D

第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