描述

圣诞老人共有M个饼干，准备全部分给N个孩子。每个孩子有一个贪婪度，第 i 个孩子的贪婪度为 g[i]。如果有 a[i] 个孩子拿到的饼干数比第 i 个孩子多，那么第 i 个孩子会产生 g[i]*a[i]的怨气。给定N、M和序列g，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小。1≤N≤30, N≤M≤5000, 1<=gi<=10^7。

输入格式

第一行两个整数N,M，第二行N个整数g1~gN。

输出格式

第一行一个整数表示答案，第二行N个整数表示每个孩子分到的饼干数。本题有SPJ，若有多种方案，输出任意一种均可。

样例输入

样例输入1
3 20
1 2 3

样例输入2
4 9
2 1 5 8

样例输出

样例输出1
2
2 9 9

样例输出2
7
​2 1 3 3

来源

ITMO

本题校验器(SPJ)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std; 
//一些定义
const int ACCEPT = 0;
const int WRONG_ANSWER = 1;
//fstd 标准输出 fout 选手输出 fin 标准输入
FILE *fstd,*fout,*fin;
int n, m, ans, val, c[32], g[32];

//执行比较操作。
bool DoCompare(){
    fscanf(fin, "%d%d", &n, &m);
    for (int i = 1; i <= n; i++) fscanf(fin, "%d", &g[i]);
    fscanf(fstd, "%d", &ans);
    fscanf(fout, "%d", &val);
    // 答案不对 
    if (ans != val) return false;
    for (int i = 1; i <= n; i++) {
		fscanf(fout, "%d", &c[i]);
		// 每个孩子分到正整数块饼干 
		if (c[i] <= 0) return false;
		m -= c[i];
	}
	// 饼干没有分完 
	if (m) return false;
	// 检查方案的怨气值是否等于输出的值 
    for (int i = 1; i <= n; i++) {
    	int cnt = 0;
    	for (int j = 1; j <= n; j++) if (c[j] > c[i]) cnt++;
    	val -= cnt * g[i];
    }
	return val == 0;
}

int main(int argc, char* argv[])
{
    if(argc!=4){
        printf("参数不足 %d",argc);
        return -1;
    }

    //打开文件
    if(NULL==(fstd=fopen(argv[1],"r"))){
        return -1;
    }
    if(NULL==(fout=fopen(argv[2],"r"))){
        return -1;
    }
    if(NULL==(fin=fopen(argv[3],"r"))){
        return -1;
    }

    if(DoCompare()){
        return ACCEPT;
    }else{
        return WRONG_ANSWER;
    }
}