2023NOIP A层联测25-游戏

link

二分答案 $mid$，看学生是否能让期望被抓人数 $\le mid$，那么老师一定不会去抓人数 $\le mid$ 的房间，学生只需管其他的房间。

由于局面对于双方来说都是不确定的，学生不知道老师抓谁，老师也不知道学生进那个房间，双方都没有固定的最佳策略。

不妨设学生有 $p_i$ 的概率进入第 $i$ 个房间，那么老师去抓第 $i$ 个房间期望人数为 $(1-p_i)a_i$，满足 $(1-p_i)a_i\le mid$，那么 $p_i\ge 1-\frac{mid}{a_i}$。对后者求和，如果小于 $1$，说明学生还有余力，还能让被抓的人变小；当等于 $1$ 时，就是答案。

下面证明这是正确的。设有 $m$ 个人数 $>mid$ 的 $a_i$，如果 $\sum (1-\frac{mid}{a_i})=m-mid\sum \frac{1}{a_i}=1$，得到 $mid=\frac{m-1}{\sum \frac{1}{a_i}}$，令老师这样决策：以 $\frac{1}{a_x\sum \frac{1}{a_i}}$ 的概率进入第 $x$ 个房间（显然总的概率之和是等于 $1$ 的），这样老师抓到的期望人数为 $\sum \frac{(1-p_x)a_x}{a_x(\sum \frac{1}{a_i})}=mid$，得证。

直接二分做就行。另外由于 $mid=\frac{m-1}{\sum \frac{1}{a_i}}$，所以可以枚举 $m$，不用二分。

下面代码实现是二分做法。

#include
using namespace std;
int n,a[100];
bool check(double mid)
{
    double sum=0;
    for(int i=1;i<=n;i++){
        if(a[i]>mid){
            sum+=1-mid/a[i];
        }
    }
    if(sum<1) return 0;
    return 1;
}
int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    double l=0,r=100;
    while(fabs(r-l)>1e-9){
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.10lf",(l+r)/2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29