AT_abc461_c [ABC461C] Variety
题目描述
There are $ N $ gems. The color (represented as an integer) of the $ i $ -th gem is $ C_i $ and its value is $ V_i $ .
Choose $ K $ gems from these $ N $ gems. Here, the chosen gems must have at least $ M $ distinct colors.
Find the maximum possible total value of the chosen gems. (Such a choice is always possible in the given input.)
输入格式
The input is given from Standard Input in the following format:
$ N $ $ K $ $ M $
$ C_1 $ $ V_1 $
$ C_2 $ $ V_2 $
$ \vdots $
$ C_N $ $ V_N $
输出格式
Output the maximum possible total value of the chosen gems as an integer.
输入输出样例 #1
输入 #1
5 3 2
1 30
1 40
1 50
2 10
3 20
输出 #1
110
输入输出样例 #2
输入 #2
5 3 3
1 30
1 40
1 50
2 10
3 20
输出 #2
80
输入输出样例 #3
输入 #3
5 5 1
4 1000000000
5 1000000000
4 1000000000
5 1000000000
4 1000000000
输出 #3
5000000000
说明/提示
Sample Explanation 1
In this sample, choose three gems from five gems. The chosen gems must have at least two distinct colors.
Choosing gems $ 2, 3, 5 $ gives colors $ 1, 1, 3 $ , which are two distinct colors. Their total value is $ 40 + 50 + 20 = 110 $ , and this is the maximum possible value.
Sample Explanation 2
The gems and the number to choose are the same as in Sample Input 1, but the chosen gems must have at least three distinct colors.
Choosing gems $ 3, 4, 5 $ gives colors $ 1, 2, 3 $ , which are three distinct colors. Their total value is $ 50 + 10 + 20 = 80 $ , and this is the maximum possible value.
Sample Explanation 3
Beware of overflow.
Constraints
- $ 1 \leq M \leq K \leq N \leq 2 \times 10^5 $
- $ 1 \leq C_i \leq N $
- $ 1 \leq V_i \leq 10^9 $
- There exist gems of at least $ M $ distinct colors.
- All input values are integers.
思路描述
比较容易想到的一题。
由于要求最大的价值，所以按价值从大到小排序。
因为至少要有 $ M $ 种宝石，所以先选出排完序后的、选出最大的、颜色互不相同的 $ M $ 颗宝石。最后再在没选过的宝石中选出 $ K-M $ 颗没选过的宝石就行了。
代码示例
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
int n,m,k,c,v,cnt;
ll ans;
pair<int,int> a[N];
set<int> st;
bool f[N];
int main() {scanf("%d %d %d",&n,&k,&m);for(int i=1;i<=n;i++) {scanf("%d %d",&c,&v);a[i].first=v;a[i].second=c;}sort(a+1,a+1+n);for(int i=n;i>=1;i--) {if(st.size()==m) break;if(st.find(a[i].second)==st.end()) {st.insert(a[i].second);f[i]=true;ans+=(ll)a[i].first;cnt++;}}for(int i=n;i>=1;i--) {if(f[i]) continue;if(cnt==k) break;ans+=(ll)a[i].first;cnt++;}printf("%lld",ans);return 0;
}