牛客多校第四场 G Maximum Mode

链接：https://www.nowcoder.com/acm/contest/142/G
来源：牛客网

The mode of an integer sequence is the value that appears most often. Chiaki has n integers a₁,a₂,...,a_n. She woud like to delete exactly m of them such that: the rest integers have only one mode and the mode is maximum.

输入描述:

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers n and m (1 ≤ n ≤ 10⁵, 0 ≤ m < n) -- the length of the sequence and the number of integers to delete.
The second line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹) denoting the sequence.
It is guaranteed that the sum of all n does not exceed 10⁶.

输出描述:

For each test case, output an integer denoting the only maximum mode, or -1 if Chiaki cannot achieve it.

示例1

输入

输出

题意：给出一个n个数的序列，我们可以删除m个数，然后我们要求出现次数最多并且最大的，

也就是如果出现次数最多的有多个，那就必须删除其他的数，避免出现次数最大的有多个，然后我们要求值最大，所以我们还要尽量判断值大的

例如输入 7 3

　　 2 2 2 2 4 4 5

出现次数最多的是2，但是我们可以删去3个2然后就可以取4了，有人会问为什么不取5呢，

因为我们最多删三次，我们要使5是出现次数最多并且没有重复的，只能把其他6个数都删了，

但是次数不够，所以不行

思路：既然我们要取次数最多并且值最大的，如果我们取当前这个数的话，我们肯定出现次数相同还有重复的话，我们优先肯定是取最大的，但是我们又要把

所有次数比他多的删掉，因为取这个数就代表当前这个数的出现次数最多，但是我们不知道哪些比它多，我们直接遍历的话会超限，所以我们贪心，先用map

记录下每个数出现的次数，然后我们用迭代器遍历，按次数最多的排前，然后次数相等的把大的排后面

（因为我们是按次数从大到小排的，所以我们要把前面那些次数比当前位置多的都减成比他小，但是相同次数的时候我们取值大的，所以次数相等的时候按值的升序排）

具体看代码的注释

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
struct sss
{
    ll x,y;
    sss(){};
    sss(ll a,ll b){x=a;y=b;};
}a[100010];
int cmp(struct sss x,struct sss y)
{
    if(x.y==y.y)
    return x.x<y.x;
    return x.y>y.y;
}
int main()
{
    int t;
    int n,m;
    map<ll,ll> mp;
    scanf("%d",&t);
    while(t--)
    {
        mp.clear();
        ll x;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)//记录每个数的出现次数
        {
            scanf("%lld",&x);
            mp[x]++;
        }
        int cnt=0;
        for(map<ll,ll>::iterator it=mp.begin();it!=mp.end();it++)//把每个数及其出现次数取出来
        {
            a[cnt].x=it->first;
            a[cnt++].y=it->second;
        }
        sort(a,a+cnt,cmp);//贪心按次数从高到低，相等值升序排序
        ll sum=0;
        ll flag=0,num=0;//sum记录的是前面总的出现次数
        for(int i=0;i<cnt;i++)
        {
            if(i<cnt-1&&a[i].y==a[i+1].y)//判断次数是否是相等的，相等的时候直接取最大的那个，(一定要加i<cnt-1，没加wa了，然后一直找错（>_<） ,,)
            {
                sum+=a[i].y;//累加次数
                continue;
            }
            else{
                if(flag==0)//第一个直接取
                {
                    if(sum-i*(a[i].y-1)<=m)//判断是否可以删除这么多数
                    {
                        flag=1;
                        num=a[i].x;  　//num存的是答案
                    }
                }
                else{
                    if(a[i].x>num)　　//我们贪心取答案最大的，然后我们再判断是否可以删这么多
                    {
                        if(sum-i*(a[i].y-1)<=m)
                        {
                            flag=1;
                            num=a[i].x;
                        }
                    }
                }    
                sum+=a[i].y;            
            }
        }
        if(flag==0) printf("-1
");
        else printf("%lld
",num);
    }
}