题解：AT_abc461_c [ABC461C] Variety

cqbz_yoyo · 2026-06-07 10:12:27 · 题解

思路

题目叫我们在取出的宝石颜色种类至少为 M 的情况下获得最大价值。

我们发现我们可以使用贪心。

我们首先考虑的就是如何在获取 M 种不同颜色的情况下得到的价值最大且取到的宝石数最小（这样我们可以之后取得更优）。

仔细想想是不是只需要把每个颜色的价值最大的宝石拿出来，再在它们里面取 M 个最大的。

好满足了题目的颜色条件，我们剩下的就全部选最大的即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void fast(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}
int n,k,m;
struct dy{
    int c,w;
}a[200005];
unordered_set<int> s;
vector<int> b[200005];
bool cmp(int x,int y){
    return x>y;
}

struct e{
    int z,i;
};
bool cmp1(e x,e y){
    return x.z>y.z;
}
bool vis[200005];
signed main(){
    fast();
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].c>>a[i].w;
        s.insert(a[i].c);
        b[a[i].c].push_back(a[i].w);
    }
    vector<e> ma;
    vector<int> all;
    for(int i:s){
        sort(b[i].begin(),b[i].end(),cmp);
        ma.push_back({b[i][0],i});

    }
    sort(ma.begin(),ma.end(),cmp1);

    int ant=0;
    for(int i=0;i<m;i++){
        ant+=ma[i].z;
        vis[ma[i].i]=1;
    }
    for(int i:s){
        int f=1;
        if(vis[i]==1){
            f=0;
        } 
        for(int j:b[i]){
            if(f==0){
                f=1;
            }else{
                all.push_back(j);
            }
        }
    }
    sort(all.begin(),all.end(),cmp);
    for(int i=0;i<k-m;i++){
        ant+=all[i];
    }
    cout<<ant;

}