2023NOIP A层联测25 T2 游戏
优秀且新颖的期望题。
思路
分析问题，由于双方都是最优策略，所以可以说学生知道老师会选择那些教室设置概率（概率设置好就不能改变），老师也知道学生会怎样选择教室（不是知道一定会去那个）。
设老师选择的集合是 \(S\)。
那么老师在学生不清空的情况下，老师的期望为 \(\sum_{i\in S} p_ia_i\)（\(p_i\) 是概率）。
学生知道每一项 \(i\) 的贡献，所以由于学生要使老师的期望最小，那么学生肯定选 \(\max(p_ia_i)\)。
于是答案为 \(\sum_{i\in S} p_ia_i-\max(p_ia_i)\)。
对于最大的那一项 \(p_ia_i\) 来说，由于他们肯定会被选走，所以说老师不妨把 \(p_i\) 改小一点，多出来的概率分给其他的数，虽然总和减小了，但被减掉的部分也减小了，而且不会被减掉的部分增加了，所以答案将获得最优。
那么最好情况下，我们要使得 \(\sum_{i \in S} p_i=1\) 且对于任意 \(i\) 而言 \(p_ia_i\) 相等。
可以构造
\[p_k=\frac{\frac{1}{a_k}}{\sum_{i \in S} \frac{1}{a_i}}
\]
这个 \(p_k\) 是符合条件的。
现在问题变为要怎样是答案最大。
答案最大要是 \(p_i\) 最小，\(p_i\) 最小要使 \(\sum_{i \in S} \frac{1}{a_i}\) 最小，也就是使 \(\sum a_i\) 最大。
设集合 \(S\) 有 \(m\) 个数，那么取最大 \(m\) 个即可。
而且这样答案合式可化为：
\[\sum_{i\in S} p_ia_i-\max(p_ia_i)=\frac{m}{\sum_{i \in S} \frac{1}{a_i}}-\frac{1}{\sum_{i \in S} \frac{1}{a_i}}=\frac{m-1}{\sum_{i \in S} \frac{1}{a_i}}
\]
对答案排序后，枚举 \(m\) 即可。
CODE
#include<bits/stdc++.h>
using namespace std;
int n;
int a[55];
double ans,sum;
bool cmp(int a,int b){return a>b;}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++) sum+=1.0/a[i],ans=max(ans,(i-1)/sum);
printf("%.12lf",ans);
}