链接：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. 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.
case：
input：
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
output：
-1
3
3
3
4
题目大意：
给N个数， 删掉M个数，使得剩下的数众数最大，求那个众数。
官方题解：
•枚举答案，考虑需要删⼏几个数才能使之变成众数
•出现次数多余它的都要被删到次数比它小
•剩下的随便便删
大概思路（本人理解）：
枚举出现的次数，因为出现次数多的更有可能成为众数，所以从多到少枚举出现的次数，其次就是相同出现次数的话取最大的那个（也有可能是由比它出现多的减过来的），简单来说就是用M次删除把最大的那个众数弄出来。
不过要注意一点就是：优化输入！！！本人没有优化输入前TLE了五次，当然，这里包括了更傻的每个案例都重新定义映射和动态数组，想这样省略初始化，但是太慢了。。。还是老老实实初始化的好。（哎，都在代码里了）
AC code：
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define ll long long int
using namespace std; const int MAXN = 1e5+; ll a[MAXN]; ///原序列
ll c[MAXN]; ///c[x]出现次数为 X 的最大值
ll T_case, N, K;
vector<ll> num_len[MAXN]; ///出现次数为 X 的数有多少个
map<ll, ll> mmp; ///记录出现次数 inline ll read() ///优化输入
{
register ll c = getchar(), flag = , sum = ;
while(c > '' || c < '')
{
if(c == '-') flag = -;
c = getchar();
}
while(c <= '' && c >= '')
{
sum = sum*+c-'';
c = getchar();
}
return flag*sum;
} int main()
{
scanf("%lld", &T_case);
while(T_case--)
{
N = read(); K = read();
mmp.clear();
for(ll i = ; i <= N; i++)
{
num_len[i].clear();
c[i] = ;
} for(int i = ; i <= N; i++)
{
a[i] = read();
if(mmp.count(a[i]) == ) mmp[a[i]] = ;
else mmp[a[i]]++;
} for(int i = ; i <= N; i++)
{
ll x = mmp[a[i]]; ///a[i]出现的次数
if(x)
{
num_len[x].push_back(a[i]); ///增加出现次数为 x 的元素
c[x] = max(c[x], a[i]); ///更新出现次数为 X 的最大值
mmp[a[i]] = ; ///出现次数清零，避免重复加
}
}
ll res = -; ///当前满足成为众数的最大值
ll pre = ; ///使当前的数成为众数的需要的删除次数
ll ans = -; ///答案
for(int len = N; len > ; len--) ///枚举出现次数
{
ll xx = num_len[len].size(); ///出现次数为len的数量
pre+=xx;
if(xx)
{
res = max(res, c[len]); ///当前的众数有可能由上一个众数退化而来
if(pre- <= K) ///如果剩余的删除次数满足需要删除次数的条件
{
ans=max(ans, res); ///更新答案
}
else break; ///剩余的删除次数无法满足当前长度众数的要求的，那之后的也无法满足了
}
K-=pre;
if(K<) break; ///无剩余操作次数
}
printf("%lld\n", ans);
}
return ;
}