牛客网暑期ACM多校训练营（第四场）G Maximum Mode（思维）

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

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

The mode of an integer sequence is the value that appears most often. Chiaki has n integers a1,a2,...,an. 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 ≤ 105, 0 ≤ m < n) -- the length of the sequence and the number of integers to delete.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) denoting the sequence.
It is guaranteed that the sum of all n does not exceed 106.

输出描述:

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

 

示例1

输入

复制

5
5 0
2 2 3 3 4
5 1
2 2 3 3 4
5 2
2 2 3 3 4
5 3
2 2 3 3 4
5 4
2 2 3 3 4

输出

复制

-1
3
3
3
4

题意：给你n个数，你要删除m个数，使得剩下的数出现次数最多的数（众数）最大。

思路：用vector[i]存出现i次的数有哪一些，然后维护一下前缀和，从n次到1次依次枚举，符合条件就取最大值，否则跳出。

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
inline ll read()
{
    register ll c=getchar(),fg=1,sum=0;
while(c>'9'||c<'0') {
if(c == '-')fg = -1;c=getchar();}
while(c<='9'&&c>='0'){sum=sum*10+c-'0';c=getchar();}
    return fg*sum;
}
const int maxn=100010;
ll n,m,k;
ll a[maxn];
ll c[maxn];
vector<ll>vc[maxn];
ll ans,ct,cnt,tmp,flag;
map<ll,ll>mp;
void init(ll n)
{
    mp.clear();
    for(ll i=0;i<=n+5;i++)
    {
    vc[i].clear();
    c[i]=0;
    }
}
int main()
{
    ll T;
    T=read();
    while(T--)
    {
        n=read();m=read();
        init(n);
        for(ll i=1;i<=n;i++)
        {
            a[i]=read();
            if(mp.count(a[i])==0)mp[a[i]]=1;
            else mp[a[i]]++;
        }
        for(ll i=1;i<=n;i++)
        {
         ll x=mp[a[i]];
         if(x) {
             vc[x].push_back(a[i]);
             c[x]=max(c[x],a[i]);
             mp[a[i]]=0;
             }
        }
        ll ma=-1;
        ll pre=0;
        ans=-1;
        for(ll i=n;i>0;i--)
        {
            ll xx=vc[i].size();
            pre+=xx;
            if(xx){
            ma=max(ma,c[i]);
            if(pre-1<=m)
            {
                ans=max(ans,ma);
            }
            else break;
        }
        m-=pre;//刚开始这里不小心写在上面括号里面，无辜多了7发WA！！！
        if(m<0) break;
        }
        printf("%lld\n",ans);
      //  if(flag) puts("Yes"); else puts("No");
    }
    return 0;
}