Codeforces Round #375 (Div. 2) Polycarp at the Radio 优先队列模拟题 + 贪心
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 = 2000 + 20; 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 = 1; i <= n; ++i) { scanf("%d", &a[i]); if (a[i] <= m) { book[a[i]]++; } } for (int i = 1; i <= m; ++i) { que.push(node(book[i], i)); } int tochange = 0; int get = n / m; for (int i = 1; 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, 0, sizeof book); while (!que.empty()) { struct node t = que.top(); que.pop(); book[t.id] = t.num; } int all = 0; int ans = inf; for (int i = 1; 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 = 1; 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 = 1; i <= n; ++i) { printf("%d ", a[i]); } return; } int main() { #ifdef local freopen("data.txt","r",stdin); #endif work(); return 0; }
感觉写的有点麻烦，
所以重写了一次。
考虑到它一定要使得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 = 2000 + 20; 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 = 1; i <= n; ++i) { scanf("%d", &a[i]); if (a[i] <= m) { book[a[i]]++; } } for (int i = 1; i <= n; ++i) { if (a[i] <= m && book[a[i]] < gold) { pos.insert(a[i]); } } for (int i = 1; i <= m; ++i) { if (book[i] < gold) pos.insert(i); } // printf("ff"); int toChange = 0; set<int> :: iterator it = pos.begin(); if (it != pos.end()) { //如果需要调整 int val = *it; for (int i = 1; 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 ", gold, toChange); for (int i = 1; i <= n; ++i) { printf("%d ", a[i]); } return ; } int main() { #ifdef local freopen("data.txt","r",stdin); #endif work(); return 0; }