欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-02 22:09:26
...

链接: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;
}

 

相关标签: ACM