/* Polycarp is a music editor at the radio station. He received a playlist for tomorrow, that can be represented as a sequence a1, a2, …, an, where ai is a band, which performs the i-th song. Polycarp likes bands with the numbers from 1 to m, but he doesn’t really like others.
We define as bj the number of songs the group j is going to perform tomorrow. Polycarp wants to change the playlist in such a way that the minimum among the numbers b1, b2, …, bm will be as large as possible.
Find this maximum possible value of the minimum among the bj (1 ≤ j ≤ m), and the minimum number of changes in the playlist Polycarp needs to make to achieve it. One change in the playlist is a replacement of the performer of the i-th song with any other group.
Input The first line of the input contains two integers n and m (1 ≤ m ≤ n ≤ 2000).
The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 109), where ai is the performer of the i-th song.
Output In the first line print two integers: the maximum possible value of the minimum among the bj (1 ≤ j ≤ m), where bj is the number of songs in the changed playlist performed by the j-th band, and the minimum number of changes in the playlist Polycarp needs to make.
In the second line print the changed playlist.
If there are multiple answers, print any of them.
*/ //题目大意：有一个序列有n个数，现在想将这n个数进行改动使其包含1道m这些数字，且使得1道m这些数字出现次数最小的数字出现次数尽可能大。问这个出现次数，以及将这个序列改为这样的序列的最少改动次数
//解题思路：实际上这个数字就是n/m。于是将1道m出现次数小于n/m的将其固定住，统计1道m的出现个数计做Cnt[i]，表示i出现次数。 便利Cnt[],如果Cnt[i]
#include<iostream> #include<cstdio> using namespace std; const int maxn = 2007; int D[maxn]; int C[maxn]; bool Fix[maxn]; int main() { int n, m; cin >> n >> m; int a = n%m; int b = m - a; int an = n / m + 1; int bn = n / m; int ta = a; int tb = b; for (int i = 0; i<n; i++) { scanf("%d", D + i); if(D[i]<=m) { C[D[i]]++;//如果是合法数字，且出现次数小于bn就固定住 if (C[D[i]] <= bn)//这一位可以确定是不动的 { Fix[i] = 1; } } } /* for (int i = 1; i <= m; i++) { if (C[i] >= an&&ta) { ta--; for (int j = n - 1; j >= 0; j--) { if (D[j] == i) { Fix[j] = 1; break; } } } } */ int ans = 0; for (int i = 1, j = 0; i <= m; i++) { int lim = n / m; /* if (ta) { lim += 1; ta--; } */ for (int cc = C[i]; j<n&&cc<lim; j++) { if (!Fix[j]) { D[j] = i; ans++; cc++; } } } cout << n / m << " " << ans << endl; for (int i = 0; i<n; i++) { if (i) cout << " "; cout << D[i]; } cout << endl; return 0; }还剩994道
