本题翻译自 [USACO 2010 Feb S] Chocolate Eating 。 贝茜收到了 块巧克力,第 块巧克力能够提供给她 点快乐值。 贝茜的初始快乐值为 ,每天结束前她会按照计划吃下若干块巧克力并获得快乐值,第二天开始时,由于经过了一整晚的睡眠,快乐值会减半(向下取整)。她想在接下来的 天内合理安排食用计划,使得这段时间内每天的最小快乐值最大。特别的,她必须按照顺序依次吃巧克力;每一天可以吃若干块巧克力、也可以不吃。 请你帮助她确定每一块巧克力都应该在哪一天吃掉,以使得这段时间内每天结束时的最小快乐值最大。
输入描述:
第一行输入两个整数 代表巧克力的数量、你需要指定计划的天数。第二行输入 个整数 代表每块巧克力的快乐值。


输出描述:
第一行输出一个整数,代表贝茜在这 天内每天结束时的最小快乐值的最大值。随后 行,第 行输出一个整数 ,代表第 块巧克力应该在哪一天吃掉。这里的编号即输入顺序,从 开始。如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。
示例1

输入

5 5
10
40
13
22
7

输出

24
1
1
3
4
5

说明

\hspace{15pt}在这个样例中:
\hspace{23pt}\bullet\,她将在第一天结束前吃掉前两块巧克力,这天的快乐值为 10+40=50
\hspace{23pt}\bullet\,第二天开始时,快乐值减半为 \frac{50}{2}=25 ,而这一条她将不再额外吃巧克力,所以这天的快乐值就为 25
\hspace{23pt}\bullet\,第三天开始时,快乐值减半为 \frac{25}{2}=12 ,与此同时她将吃掉第三块巧克力,这天的快乐值为 12+13=25
\hspace{23pt}\bullet\,第四天开始时,快乐值减半为 \frac{25}{2}=12 ,与此同时她将吃掉第四块巧克力,这天的快乐值为 12+22=34
\hspace{23pt}\bullet\,第五天开始时,快乐值减半为 \frac{34}{2}=17 ,与此同时她将吃掉第五块巧克力,这天的快乐值为 17+7=24
\hspace{15pt}综上所述,贝茜在这 5 天内每天结束时的最小快乐值为 \min\left\{25, 25, 34, 24\right\}=24 ,我们可以证明这是最大的。
加载中...