ASimpleProblemaboutelection

ZZZZSGW is a cute hamster living in a beautiful city named WWW. However, the COVID-19 spread like a wild fire in his city, many people infected. With great grief and motivation, he really wants to do something for his hometown. Therefore he applied for the volunteer of his community to help his neighbors.

There are $n$ candidates and the voluntary team only needs several volunteers in total. To ensure the quality of the team, they decided to hold an election to pick out the volunteers. Every resident has to nominate exactly $m$ candidates and mustn't give more than one nomination to each candidate. (of course one can save one of the nominations for himself/herself). The candidates then will be ranked by the nominations they get in descending order, if there are candidates have the same number of nominations, they will be ranked by their names in lexicographically increasing order.

It's evident that the name ZZZZSGW won't take much chance, so when he has the same nominations with others, you can just suppose that he will always be the last! What's worse, the order to nominate is also according to the names, which means that this poor guy will also be the last one to make his decision among the residents!

However, as each coin has two sides, the last to make decision also means the one who knows everything ------ since everyone can see the current result when making nominations! Now it's ZZZZSGW's turn, he knows the current result and the final result only depends on his own decision. But he is too nervous to make a clear judgment! Can you help him to get the highest place under this situation?

The input consists of several test cases. The first line of the input is an integer $T$ , the number of the test cases.

For each test case, the first line will be two integers $n,m$ . The number of candidates and the number of nominations that each resident can make.

The next line will be $n$ integers $\{a_1,a_2,...,a_n\}$ separated by spaces, which are the current number nominations of each candidate. The first integer always refers to the nominations of ZZZZSGW.

For each test case, $0\le a_i \le 10^9$ , $1\le m \le n \le 10^5$ . And there is $\sum n \le 2*10^5$ for all test cases.

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int a[100010]; int main(){ int t,n,m; cin>>t; while(t--){ int sum1=0,sum2=0; cin>>n>>m; scanf("%d",&a[1]); for(int i=2;i<=n;++i){ scanf("%d",&a[i]); if(a[i]>a[1]) sum1++; else if(a[i]<a[1]) sum2++; } if(m-1<=sum1+sum2) cout<<sum1+1<<endl; else cout<<m-sum2<<endl; } }

#include<bits/stdc++.h> using namespace std; int a[100005],n,m;; void work(){ scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%d",a+i); int x=a[0]; sort(a,a+n),a[n]=1e9+5; int y=upper_bound(a,a+n+1,x-1)-a,z=upper_bound(a,a+n+1,x)-a,num=n-z+y; if(num>=m-1)printf("%d\n",n-z+1); else printf("%d\n",n-z+m-num); } int main(){ int T;scanf("%d",&T); while(T--)work(); }

详情