#188. 饼干

饼干

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

圣诞老人共有M\red{M}个饼干,准备全部分给N\red{N}个孩子。

每个孩子有一个贪婪度,第 i\red{i} 个孩子的贪婪度为 gi\red{g_i}

如果有 ai\red{a_i} 个孩子拿到的饼干数比第 i\red{i} 个孩子多,那么第i\red{ i} 个孩子会产生 gi×ai\red{g_i\times a_i}的怨气。

给定NM\red{N、M}和序列g\red{g},圣诞老人请你帮他安排一种分配方式,使得每个孩子至少分到一块饼干,并且所有孩子的怨气总和最小。

输入格式

第一行包含两个整数N,M\red{N,M}

第二行包含N\red{N}个整数表示g1 gN\red{g_1~g_N}

输出格式

第一行一个整数表示最小怨气总和。

第二行N\red{N}个空格隔开的整数表示每个孩子分到的饼干数,若有多种方案,输出任意一种均可。

此题有spj,任意一种形式的答案都为正确此题有\red{spj},任意一种形式的答案都为正确

输入样例

3 20
1 2 3

输出样例

2
2 9 9

提示

1N30\red{1≤N≤30},

NM5000\red{N≤M≤5000},

1gi107\red{1≤g_i≤10^7}

周日下午线上班2(周日下午讲解题目)

未参加
状态
已结束
规则
ACM/ICPC
题目
5
开始于
2021-9-21 17:00
结束于
2021-9-30 1:00
持续时间
200 小时
主持人
参赛人数
3