C. Elections

题目链接

Codeforces Round #503 (by SIS, Div. 2)--C. Elections

题解

中档题。某地区有一堆政党与一群人,每个人会投票给某个政党,要改变某人的投票需要一定费用。当且仅当某个政党的票数严格大于其他政党才能胜利。现在你属于某一政党,计算所需要花费最少代价来使所在政党获得胜利。
枚举每一种所需的最高票数,如果某一个其他政党的票数大于枚举的票数,则顺次收买最便宜的人。如果收买完之后票数不够顺次收买其他所有政党最便宜的人。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 3005;
int input[MAXN][MAXN], c[MAXN], q[MAXN], n, m;
long long get(int k) {
    long long ret = 0, cnt = 0;
    int tt = 0;
    for (int i = 2; i <= m; i++) {
        if (c[i] >= k) {
            int now = c[i] - k + 1;
            for (int j = 1; j <= now; j++)ret += input[i][j];
            for (int j = now + 1; j <= c[i]; j++)q[++tt] = input[i][j];
            cnt += now;
        }
        else {
            for (int j = 1; j <= c[i]; j++)q[++tt] = input[i][j];
        }
    }
    if (cnt + c[1] < k) {
        int now = k - c[1] - cnt;
        sort(q + 1, q + tt + 1);
        for (int i = 1; i <= now; i++)ret += q[i];
    }
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int x, y; scanf("%d%d", &x, &y);
        input[x][++c[x]] = y;
    }
    for (int i = 1; i <= m; i++) {
        sort(input[i] + 1, input[i] + 1 + c[i]);
    }
    long long ans = 1e16;
    for (int i = 1; i <= n; i++)
        ans = min(ans, get(i));
    cout << ans << endl;
    return 0;
}

标签: greedy

添加新评论