Codeforces Round #503 C. Elections

Codeforces Round #503 C. Elections

枚举2~m的最大票数，对于枚举的每个票数i，可以用优先队列以最小的代价构造出1号的胜局，然后在所有最小代价中取最小值即可

#include using namespace std;typedef long long ll;const int maxn = 3010;const ll INF = 1e16;vector v[maxn];vector sum[maxn];int pos[maxn];struct Node{ int val, id; bool operator < (const Node &t) const { return val > t.val; }} node;int main(){ int n, m; scanf("%d%d", &n, &m); int h1 = 0, maxh = 0; for (int i = 1; i <= n; i++) { int x, y; scanf("%d%d", &x, &y); v[x].push_back(y); if (x == 1) h1++; } for (int i = 2; i <= m; i++) { sort(v[i].begin(), v[i].end()); ll t = 0; for (int j = 0; j < v[i].size(); j++) { t += v[i][j]; sum[i].push_back(t); } maxh = max(maxh, (int)v[i].size()); } if (h1 > maxh) { printf("0\n"); return 0; } ll ans = INF; for (int i = h1; i <= maxh; i++) { for (int j = 2; j <= m; j++) pos[j] = 0; int h = h1; ll cost = 0; for (int j = 2; j <= m; j++) { if (v[j].size() > i) { pos[j] = v[j].size()-i; h += (v[j].size()-i); cost += sum[j][pos[j]-1]; } } if (h >= i + 1) { ans = min(ans, cost); continue; } priority_queue que; for (int j = 2; j <= m; j++) { if (pos[j] < v[j].size()) que.push(Node{v[j][pos[j]], j}); } int need = i+1-h; while (need) { if (que.empty()) break; node = que-(); que.pop(); cost += node.val; int p = node.id; pos[p]++; if (pos[p] < v[p].size()) que.push(Node{v[p][pos[p]], p}); need--; } if (need == 0) ans = min(ans, cost); } printf("%I64d\n", ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。