题目描述
给你一个整数序列 \(A=(A_1,A_2,...,A_N)\) 。
请你执行以下操作恰好 \(K\) 次后，求序列 \(A\) 中所有元素的最小可能和。
- 选择一个整数 \(x\) 。对于所有满足 \(A_i=x\) 的位置 \(i\) ，将 \(A_i\) 的值替换为 \(0\) 。
约束条件
- \(1 \le K \le N \le 3 \times 10^5\)
- \(1 \le A_i \le 10^9\)
- 所有输入值均为整数。
输入格式
\(N\) \(K\)
\(A_1\) \(A_2\) \(...\) \(A_n\)
输出格式
输出最终答案。
样例
Input 1
6 2
7 2 7 2 2 9
Output 1
6
Input 2
8 6
1 2 3 4 1 2 3 4
Output 2
0
Input 3
10 2
3 3 4 1 1 3 3 1 5 1
Output 3
8
思路概述
因为删除过程是要删同一个数，所以直接造结构体，储存数、出现次数；
又因为我们要使结果尽可能小，所以我们要删贡献值最大的数（若数为 \(A\) ，且出现 \(cnt\) 次，那么贡献值为 \(A \times cnt\)）。直接对结构体排序即可解决。
代码
#include <bits/stdc++.h>
#define ll long long
#define N 300010
using namespace std;
struct node {int num;int cnt;ll sum;bool operator<(const node &T)const {return sum<T.sum;}
};
int n,k,b[N],tot;
node a[N];
ll ans;
int main() {ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++) cin>>b[i];sort(b+1,b+1+n);for(int i=1;i<=n;i++) {if(a[tot].num!=b[i]) {a[++tot].num=b[i];a[tot].cnt=a[tot].sum=0;}a[tot].cnt++;a[tot].sum+=(ll)a[tot].num;}sort(a+1,a+1+tot);while(k--) tot--;for(int i=1;i<=tot;i++) ans+=a[i].sum;cout<<ans;return 0;
}