?

鏈接：https://www.nowcoder.com/acm/contest/142/G
來(lái)源：牛客網(wǎng)

題目描述

The mode of an integer sequence is the value that appears most often. Chiaki has n integers a₁,a₂,...,a_n. 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 ≤ 10^5, 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 ≤ 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. 示例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 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int MAXN=1e5+10; 4 int a[MAXN]; 5 map<int, int>ma; 6 map<int ,int>mb; 7 int sum[MAXN],cnt[MAXN]; 8 int main() 9 { 10 int _; 11 scanf("%d",&_); 12 while(_--) 13 { 14 ma.clear(); 15 int n,m; 16 scanf("%d%d",&n,&m); 17 for(int i=1;i<=n;i++) 18 { 19 scanf("%d",&a[i]); 20 ma[a[i]]++; 21 sum[i]=0; 22 cnt[i]=0; 23 } 24 for(auto &i:ma) cnt[i.second]++; 25 for (int i = n-1; i ; i--) { //求出后綴和 26 cnt[i]+=cnt[i+1]; 27 sum[i]=sum[i+1]+cnt[i];//從后向前進(jìn)行，如果一個(gè)數(shù)出現(xiàn)n次，在向前加的過(guò)程中就會(huì)加n次。保證后綴和正確 28 } 29 int MAX=-1; 30 for(auto &i:ma){ 31 if(sum[i.second]-1<=m) MAX=max(MAX,i.first);//枚舉答案，-1是因?yàn)橹灰ＷC當(dāng)前這個(gè)眾數(shù)比其他的多一即可 32 } 33 printf("%d\n",MAX); 34 } 35 return 0; 36 }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/-xiangyang/p/9383562.html

總結(jié)

以上是生活随笔為你收集整理的牛客第四次多校Maximum Mode的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。