http://codeforces.com/contest/723/problem/C
题目是给出一个序列
a[i]表示第i个歌曲是第a[i]个人演唱，现在选出前m个人，记b[j]表示第j个人演唱歌曲的数量，
现在你可以改变a[]这个数组，使得前m个人的演唱歌曲的数量的最小值最大。
很明显对于前m个人，每个人唱了多少首是很容易统计出来的，只需要对<=m的人进行统计即可，不用统计>m的，这样的话数组只需开到2000即可。
对于后面的人，可以改变，优先改变前m个人中演唱歌曲最小的那个，这个可以用优先队列维护。
然后如果前m个人本来分配不均匀，那么最小值的最大值得不到最大化。
要对前m个人均匀一下，这个我用了两个优先队列去做，因为思路就是把最大的分一次给最小的，这样的最优的。
hack点：注意到ans最多也只是n / m。就相当于把n分成m分，如果前m个人的答案已经是n / m，后面的人就不需要变化的，不然的话改变数量变大了，会错误。好像wa7就是这个坑。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
int n, m;
const int maxn = + ;
int book[maxn];
int a[maxn];
struct node {
int num;
int id;
bool operator < (const struct node &rhs) const {
return num > rhs.num;
}
node(int aa, int bb) : num(aa), id(bb) {}
};
struct GGnode {
int num;
int id;
bool operator < (const struct GGnode &rhs) const {
return num < rhs.num;
}
GGnode(int aa, int bb) : num(aa), id(bb) {}
};
priority_queue<struct node>que;
priority_queue<struct GGnode>GGque;
vector<int>pos[maxn];
void work() {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; ++i) {
scanf("%d", &a[i]);
if (a[i] <= m) {
book[a[i]]++;
}
}
for (int i = ; i <= m; ++i) {
que.push(node(book[i], i));
}
int tochange = ;
int get = n / m;
for (int i = ; i <= n; ++i) {
if (a[i] <= m) continue;
struct node t = que.top();
if (t.num == get) break;
que.pop();
a[i] = t.id;
t.num++;
que.push(t);
tochange++;
}
memset(book, , sizeof book);
while (!que.empty()) {
struct node t = que.top();
que.pop();
book[t.id] = t.num;
}
int all = ;
int ans = inf;
for (int i = ; i <= m; ++i) {
ans = min(ans, book[i]);
all += book[i];
que.push(node(book[i], i));
GGque.push(GGnode(book[i], i));
}
for (int i = ; i <= n; ++i) {
if (a[i] <= m) {
pos[a[i]].push_back(i);
}
}
int gold = all / m;
if (ans != gold) {
while (true) {
struct node tt = que.top();
que.pop();
struct GGnode GGtt = GGque.top();
GGque.pop();
if (book[tt.id] == gold) break; book[tt.id]++;
book[GGtt.id]--;
int tpos = pos[GGtt.id].back();
pos[GGtt.id].pop_back();
a[tpos] = tt.id; tt.num = book[tt.id];
GGtt.num = book[GGtt.id]; que.push(tt);
GGque.push(GGtt);
tochange++;
}
}
ans = gold;
cout << ans << " " << tochange << endl;
for (int i = ; i <= n; ++i) {
printf("%d ", a[i]);
}
return;
} int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
work();
return ;
}
感觉写的有点麻烦，
所以重写了一次。
考虑到它一定要使得b[j]数组中的最小值最大，而这个最大值，必然是n / m的。所以，直接把1---m中数量小于n / m的统计起来，用其他去变即可。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
int a[maxn];
int book[maxn];
set<int>pos;
void work() {
int n, m;
scanf("%d%d", &n, &m);
int gold = n / m;
for (int i = ; i <= n; ++i) {
scanf("%d", &a[i]);
if (a[i] <= m) {
book[a[i]]++;
}
}
for (int i = ; i <= n; ++i) {
if (a[i] <= m && book[a[i]] < gold) {
pos.insert(a[i]);
}
}
for (int i = ; i <= m; ++i) {
if (book[i] < gold) pos.insert(i);
}
// printf("ff");
int toChange = ;
set<int> :: iterator it = pos.begin();
if (it != pos.end()) { //如果需要调整
int val = *it;
for (int i = ; i <= n; ++i) {
if (a[i] > m) {
book[val]++;
a[i] = val;
toChange++;
} else {
if (pos.find(a[i]) != pos.end()) continue;
if (book[a[i]] == gold) continue;
book[a[i]]--;
book[val]++;
a[i] = val;
toChange++;
}
if (book[val] == gold) {
it++;
if (it == pos.end()) break;
val = *it;
}
}
}
printf("%d %d\n", gold, toChange);
for (int i = ; i <= n; ++i) {
printf("%d ", a[i]);
}
return ;
} int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
work();
return ;
}