C. Polycarp at the Radio
time limit per test
memory limit per test
input
output
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.
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
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
n and m (1 ≤ m ≤ n ≤ 2000).
n integers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is the performer of the i-th song.
Output
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.
Examples
input
4 2 1 2 3 2
output
2 1 1 2 1 2
input
7 3 1 3 2 2 2 2 1
output
2 1 1 3 3 2 2 2 1
input
4 4 1000000000 100 7 1000000000
output
1 4 1 2 3 4
题意:通过改变歌曲的演唱者，使1到m的每个band表演的歌曲数目的最小值达到最大.
显然每个band表演的歌曲数目的最小值的最大值肯定为n / m, 只要记录现在1..m每个band已经表演的歌曲数目，对于不足n / m的band, 改变大于m的band的歌曲，或者在1..m中的band演唱歌曲数大于n/m,来使歌曲数目等于n/m
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define maxn 1000005
#define MOD 1000000007
using namespace std;
typedef long long ll;
int num[2005], p[2005];
int main(){
//freopen("in.txt", "r", stdin);
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++)
scanf("%d", num+i);
int k1 = n / m;
for(int i = 0; i < n; i++){
if(num[i] <= m)
p[num[i]]++;
}
int j = 0, ans = 0;
for(int i = 1; i <= m; i++){
if(p[i] < k1){
for(; j < n; j++){
if(num[j] > m){
num[j] = i;
p[i]++;
ans++;
}
else if(p[num[j]] > k1){
p[num[j]]--;
num[j] = i;
p[i]++;
ans++;
}
if(p[i] == k1)
break;
}
}
}
printf("%d %d\n", k1, ans);
for(int i = 0; i < n; i++){
if(i != 0)
putchar(' ');
printf("%d", num[i]);
}
puts("");
return 0;
}