Participants of the Luck Competition choose a non-negative integer no more than 100 in their mind. After choosing their number, let KK be the average of all numbers, and MM be the result of K×23K×23. Then the lucky person is the one who choose the highest number no more than MM. If there are several such people, the lucky person is chosen randomly. If you are given a chance to know how many people are participating the competition and what their numbers are, calculate the highest number with the highest probability to win assuming that you're joining the competition. Input There are several test cases and the first line contains the number of the number of test cases T(T≤10)T(T≤10). Each test case begins with an integer N(1<N≤100)N(1<N≤100), denoting the number of participants. And next line contains N−1N−1 numbers representing the numbers chosen by other participants. Output For each test case, output an integer which you have chosen and the probability of winning (round to two digits after the decimal point), seperated by space. Sample Input 3 4 1 2 3 4 1 1 2 4 20 30 40 Sample Output 1 0.50 0 1.00 18 1.00
Hint
题意：
n（2~100）个人参加一个游戏， 每个人选择1~100范围的数。 然后得到所有数的平均数，再*=2/3，设得到的数为m。 如果一个人选的数，比m小，且相距m最为接近，那么其便在所有选数相同的人中等概率中奖。 现在，我们也参加比赛，其他n-1个人所选择的数也已经确定了，并且我们知道。 问你，选什么数拥有最高中奖率，并输出。
思路：
假设我们选的数为x,其他n-1个人选的数之和为sum,那么M的值为
显然,x需要满足
要使x尽可能大,不等式右侧向下取整即可
得到x之后,获奖概率取决于同样选了x的人有几个,因为x的值比较小,我们完全可以在输入的时候保存每种数出现的次数
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T,i;
cin>>T;
while(T--)
{
int t,n,sum=0,x,a[101]={0};
cin>>n;
for(i=0;i<n-1;i++)
{
cin>>t;
a[t]++;
sum+=t;
}
x=2*sum/(3*n-2);
cout<<x<<" "<<fixed<<setprecision(2)<<1.0/(a[x]+1)<<endl;
}
return 0;
}
