链接：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 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.
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+10; 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 = 1, sum = 0; while(c > '9' || c < '0') { if(c == '-') flag = -1; c = getchar(); } while(c <= '9' && c >= '0') { sum = sum*10+c-'0'; c = getchar(); } return flag*sum; } int main() { scanf("%lld", &T_case); while(T_case--) { N = read(); K = read(); mmp.clear(); for(ll i = 0; i <= N; i++) { num_len[i].clear(); c[i] = 0; } for(int i = 1; i <= N; i++) { a[i] = read(); if(mmp.count(a[i]) == 0) mmp[a[i]] = 1; else mmp[a[i]]++; } for(int i = 1; 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]] = 0; ///出现次数清零，避免重复加 } } ll res = -1; ///当前满足成为众数的最大值 ll pre = 0; ///使当前的数成为众数的需要的删除次数 ll ans = -1; ///答案 for(int len = N; len > 0; len--) ///枚举出现次数 { ll xx = num_len[len].size(); ///出现次数为len的数量 pre+=xx; if(xx) { res = max(res, c[len]); ///当前的众数有可能由上一个众数退化而来 if(pre-1 <= K) ///如果剩余的删除次数满足需要删除次数的条件 { ans=max(ans, res); ///更新答案 } else break; ///剩余的删除次数无法满足当前长度众数的要求的，那之后的也无法满足了 } K-=pre; if(K<0) break; ///无剩余操作次数 } printf("%lld ", ans); } return 0; }