题解：AT_abc461_c [ABC461C] Variety

Ethan_sun · 2026-06-07 09:33:25 · 题解

solution

赛时写的时候输入输反凭空调了 10 分钟。

考虑贪心。

由于需要 m 个颜色的宝石，所以先把每种都选一个，这里要选最大的。

接下来还剩下 k - m 个要选，再遍历一次，遇到没有选过的宝石 cnt 就加 1，答案记得也累加，直到 cnt = k 为止。

code

::::success[展开]

#include <bits/stdc++.h>
#define debug(a) cerr << (#a) << " = " << (a) << endl;
#define int long long
#define maxn 200010
#define endl '\n'
using namespace std;

int n, k, m;
bool use[maxn];
map<int, bool> mp;
struct node {
    int c, v;
} a[maxn];
bool cmp(node x, node y) {
    return x.v > y.v;
}
void solve() {
    cin >> n >> k >> m;
    for (int i = 1; i <= n; i++) cin >> a[i].c >> a[i].v;
    sort(a + 1, a + n + 1, cmp);
    int cnt = 0, ans = 0;
    for (int i = 1; i <= n && cnt < m; i++) {
        if (mp[a[i].c]) continue;
        cnt++;
        use[i] = true;
        mp[a[i].c] = true;
        ans += a[i].v;
    }
    int cntk = m;
    for (int i = 1; i <= n && cntk < k; i++) {
        if (use[i]) continue;
        cntk++;
        ans += a[i].v;
    }
    cout << ans << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; t = 1;
//  cin >> t;
    while (t--) solve();
    return 0;
}

::::