526互联

Codeforces Round 760 (Div. 3) D. Array and Operations（贪心）

发布时间 2023-03-23 16:07:56作者: 高尔赛凡尔娟

https://codeforces.com/contest/1618/problem/D

题目大意：

给定一个长度为n的数组a，我们可以进行m次操作：

每次操作可以任意选择两个不同的下标的数字x和y，并把它两删除，替换成x/y（但是x/y不可以再被选择进行除数运算了）。

问我们这样剩下来的数列的最小值是多少？

input
5
7 3
1 1 1 2 1 3 1
5 1
5 5 5 5 5
4 2
1 3 3 7
2 0
4 2
9 2
1 10 10 1 10 2 7 10 3
output
2
16
0
6
16

详解见代码内部注释

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e6+10,M=4004;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
LL a[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    cin>>T;
    while(T--)
    {
        LL n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        sort(a+1,a+1+n);
        LL res=0;
        //前面的数字从贪心的角度来说一定都是最小的，如果操作了是一定会亏损的
        for(int i=1;i<=n-2*m;i++)
        {
            res+=a[i];
        }
        map<int,int> mp;
        for(int i=n-2*m+1;i<=n;i++)
        {
            mp[a[i]]++;
        }
        int maxn=0;
        for(auto i:mp)
        {
            maxn=max(maxn,i.second);//找到相同数字的最大数量
            //其它的数量可以彼此互相抵消
        }
        if(maxn>m) res+=maxn-m;//如果数量会超过m个，说明这m个可以全部抵消，其它的数量相除==1
        cout<<res<<endl;
    }
    return 0;
}