牛客多校第四场 G Maximum Mode

Maximum Mode

问题分析

题意就是问你能否精确的删除m$m$个数，使得数列中的众数只有一个并且保证值最大化。
如果数列中众数不止一个，那么我们去考虑对于出现次数相同的数，最少删除几个数可以使得它变为众数，我们设这个最少的删除数为minDelete$minDelete$，如果此时minDelete<=m$minDelete<=m$，那么就满足条件，剩下的m−minDelete$m-minDelete$个数从剩余的数列里随便删即可。

#include <bits/stdc++.h>
#include <map>
#include <vector>

struct node{
    int cnt,v;
    node(int cnt = 0,int v = 0):cnt(cnt),v(v){};
    bool operator <(const node &u) const{
        return cnt > u.cnt;
    }
}a[100001];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m,x,ans = -1;
        std::map<int,int> mp;
        scanf("%d%d",&n,&m);
        for(int i = 0; i < n; ++i){
            scanf("%d",&x);
            mp[x]++;
        }
        std::vector<node> v;
        for(auto i : mp)
            v.emplace_back(i.second,i.first); 
        std::sort(v.begin(),v.end()); //按照出现次数由大到小排序
        for(int i = 0, k = 0, sum = 0; i < v.size(); ++i){
            while(k < v.size() && v[i].cnt == v[k].cnt)
                sum += v[k++].cnt;
            int minDelete = sum - (v[i].cnt-1)*k - 1; //使得v[i].v变成唯一的众数需要删除的数的最小个数
            if(minDelete <= m)
                ans = std::max(ans,v[i].v); //Maximum value
        }
        printf("%d\n",ans);
    }
    return 0;
}