链接：https://www.nowcoder.com/acm/contest/142/G
来源：牛客网
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
5
, 0 ≤ m < n) -- the length of the sequence and the number of integers to delete.
The second line contains n integers a
1
, a
2
, ..., a
n
(1 ≤ a
i
≤ 10
9
) denoting the sequence.
It is guaranteed that the sum of all n does not exceed 10
6
.
For each test case, output an integer denoting the only maximum mode, or -1 if Chiaki cannot achieve it.
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const ll maxn = 1e5;
const ll mod = 1e12 + 7;
struct node {
ll x, y;
};
map<ll,ll> mm;
node a[maxn+10];
bool cmp( node p, node q ) {
if( p.y == q.y ) {
return p.x > q.x;
}
return p.y > q.y;
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll T;
cin >> T;
while( T -- ) {
for( ll i = 0; i < maxn; i ++ ) {
a[i].x = a[i].y = 0;
}
mm.clear();
ll n, m, j = 0;
cin >> n >> m;
ll all = n;
for( ll i = 0, t; i < n; i ++ ) {
cin >> t;
mm[t] ++;
}
for( map<ll,ll>::iterator it = mm.begin(); it != mm.end(); it ++ ) {
a[j].x = (*it).first, a[j].y = (*it).second;
j ++;
}
sort( a, a+j, cmp );
ll num = n - m, ans = -1;
if( num == 1 ) {
ans = 0;
for( ll i = 0; i < j; i ++ ) {
ans = max( ans, a[i].x );
}
} else if( num <= j ) {
ans = 0;
for( ll i = 0; i < j; i ++ ) {
if( a[i].y >= 2 ) {
ans = max( ans, a[i].x );
} else {
break;
}
}
} else {
ll t = num - j + 1;
ans = 0;
for( ll i = 0; i < j; i ++ ) {
if( a[i].y >= t ) {
ans = max( ans, a[0].x );
} else {
break;
}
}
map<ll,ll> mp;
for( ll i = 0; i < j; i ++ ) { //记录出现次数一样的数的个数方便后面加减
mp[a[i].y] ++;
}
for( ll i = 0; i < j; i ++ ) {
if( a[i].y >= 2 ) {
if( i > 0 && a[i].y == a[i-1].y ) {
} else {
ll sum = a[i].y + i*(a[i].y-1);
if( sum >= num ) {
ans = max( ans, a[i].x );
} else {
ll allnum = all - a[i].y*mp[a[i].y];
sum += (a[i].y-1)*(mp[a[i].y]-1);
if( allnum + sum >= num ) {
ans = max( ans, a[i].x );
}
}
}
}
all -= a[i].y;
}
}
if( ans > 0 ) {
cout << ans << endl;
} else {
cout << -1 << endl;
}
}
return 0;
}
牛客网暑期ACM多校训练营（第四场） G Maximum Mode 思维
原文：https://www.cnblogs.com/l609929321/p/9383250.html