4602: Cookies
内存限制:128 MB
时间限制:1.000 S
评测方式:特殊裁判
命题人:
提交:13
解决:0
题目描述
圣诞老人共有 M个饼干,准备全部分给 N个孩子。每个孩子有一个贪婪度,第 i 个孩子的贪婪度为 g[i]。如果有 a[i]个孩子拿到的饼干数比第 i 个孩子多,那么第 i 个孩子会产生 g[i]×a[i] 的怨气。给定N、M和序列 g,圣诞老人请你帮他安排一种分配方式,使得每个孩子至少分到一块饼干,并且所有孩子的怨气总和最小。1≤N≤30,N≤M≤5000,1≤g[i]≤107 。
输入
第一行两个整数 N,M,第二行 N个整数 g1∼gN
输出
第一行一个整数表示答案,第二行 N个整数表示每个孩子分到的饼干数。本题有 SPJ,若有多种方案,输出任意一种均可。
样例输入 复制
3 20
1 2 3
样例输出 复制
4 9
2 1 5 8
提示
spj