6. 烤鱼
XJOI - 题目ID：8718必做题100分
最新提交：0 分
历史最高：0 分
时间限制: 1000ms
空间限制: 262144kB
题目描述
题目描述
小x掉到了一个WYZX的窨井里，这口井很深，没有人能听到小x的呼救，悲催的小x必须要等 �D 天后，学校确认他失踪才会大规模寻找他，而这难熬的 �D 天将是小x这一生最难过的 �D 天。 不过幸运的是小x在井里得到了 �(1≤ �≤ 50,000)N(1≤ N≤ 50,000) 条鱼,编号 1…N. 他计划在接下来的 �(1≤ �≤ 50,000)D(1≤ D≤ 50,000) 天按鱼的编号从小到大逐天吃，当然，小x可以一天连续吃多条鱼，也可以不吃。为了不浪费，小x要求鱼必须吃完。对于第 �i 条鱼，小x的能量值会增加 ��(1≤ ��≤ 1,000,000)Hi(1≤ Hi≤ 1,000,000)。小x会在白天吃鱼，一旦吃饱，他就会一觉睡到第二天。第二天醒来，她的能量值会变成前一天的能量值的一半（向下取整），小x的能量值是可以累加的。 小x比较注意维护每天能量的平衡，要刻意避免能量的大起大落，于是现在小x想知道，如何安排吃鱼，才能保证能量值最小的那个晚上(假设是第 �X 个晚上)，第 �X 个晚上的能量值最大。 例如：有5条鱼，能量值分别是： (10, 40, 13, 22, 7). 小x按以下方式吃鱼，将会得到最优值:
| 第几天 | 醒来时能量值 | 吃了鱼后能量值 | 晚上睡觉能量值 |
|---|---|---|---|
| 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≤�≤�)i (1≤i≤N) 条鱼是小x第几天吃掉的。
输入格式
第1行:两个整数: �N 和 �D
第2…N+1行: 每行一个整数 ��Hi。
输出格式
第1行: 一个整数， 在这 �D 个晚上里，能量值最小的那个晚上(假设是第 �X 个晚上)，第 �X 个晚上的能量值最大可以是多少？
第2…N+1行: 每行一个整数，第 �i 行表示第 �i 条鱼是第几天被吃的。
样例数据
input
5 5
10
40
13
22
7
output
24
1
1
3
4
5
数据规模与约定
40%40% 保证 �，�≤200N，D≤200
100%100% 数据如题目描述
时间限制：1s
空间限制：256MB
跑题了啊