Codeforces 1020C(枚举+STL)

Codeforces 1020C
题意：$n, m$代表选民和党派下面$n$个选民, $p_i$是他原本打算投的人, $c_i$是你花费这么多可以让他投你, 求最少花费

因为这题最大的麻烦之处就是如果把别的党派的弄到1去，别的党派会少1票，而1党派会多1票，形成了2的差。并且党派初始最大的可能有很多个，难以判断党派1要有多少票。
所以我们可以枚举党派1得的票，相当于枚举一个标准值，让1党派必须达到这个标准值。这与二分判定有类似的地方，我们只需要考虑1党派每种票数的最优解即可
对于处理党派票数，如果其他党派有不小于1党派的，切掉最小的那几个直到其他党派能够比1党派票数小。这个可以用multiset来维护。

知识点：对于这种无法确定个数的题目，不要乱贪心DP，可以枚举一个标准值，然后让无法确定个数变为能够确定个数，从而解决问题

//==========================Head files==========================
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
#define LL long long
#define db double
#define mp make_pair
#define pr pair<int, int>
#define fir first
#define sec second
#define pb push_back
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
//==========================Templates==========================
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
inline LL readl() {
    LL x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
inline int power(int a, int b) {
    int ans = 1;
    while (b) {
        if(b & 1) {ans = ans * a; --b;}
        b >>= 1;a = a * a;
    }
    return ans;
}
inline int power_mod(int a, int b, int mod) {
    a %= mod;
    int ans = 1;
    while (b) {
        if(b & 1) {ans = ans * a % mod; --b;}
        b >>= 1, a = a * a % mod;
    }
    return ans;
}
LL gcdl(LL a, LL b) {return b == 0 ? a : gcdl(b, a % b);}
LL abssl(LL a) {return a > 0 ? a : -a;}
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
int abss(int a) {return a > 0 ? a : -a;}
//==========================Main body==========================
#define LD "%I64d"
#define D "%d"
#define pt printf
#define sn scanf
#define pty printf("YES\n")
#define ptn printf("NO\n")
inline int read();
inline LL readl();
inline int power(int a, int b);
inline int power_mod(int a, int b, int mod);
LL gcdl(LL a, LL b);
LL abssl(LL a);
int gcd(int a, int b);
int abssl(int a);
//==========================Code here==========================
LL ans, n, m, pi[3005], ci[3005];
multiset<LL> s, tmp[3005];
LL pro(LL d) {
    LL tot = 0, cc = (int)tmp[1].size();
    s.clear();
    for (LL i = 1; i <= n; i++) if (pi[i] != 1) s.insert(ci[i]);
    for (LL i = 2; i <= m; i++) if ((int)tmp[i].size() >= d) {
        LL cnt = (int)tmp[i].size();
        for (multiset<LL>::iterator it = tmp[i].begin(); it != tmp[i].end(); it++) {
            if (cnt < d) break;
            tot += *it, cnt--, cc++;
            s.erase(s.find(*it));
        }
    }
    if (cc > d) return 9223372036854775807ll;
    for (multiset<LL>::iterator it = s.begin(); it != s.end(); it++) {
        if (cc >= d) break;
        tot += *it, cc++;
    }
    return tot;
}
int main() {
    cin >> n >> m;
    for (LL i = 1; i <= n; i++) cin >> pi[i] >> ci[i];
    ans = 9223372036854775807ll;
    for (LL i = 1; i <= n; i++) tmp[pi[i]].insert(ci[i]);
    for (LL i = 1; i <= n; i++) ans = min(ans, pro(i));
    cout << ans;
    return 0;
}