NOIP2023模拟12联测33 B. 游戏
题目大意
期望题
思路
二分答案 \(mid\) ，我们只关注学生是否能够使得被抓的人数 \(\le mid\)
那我们就只关心 \(a > mid\) 的房间就行了。
设学生有 \(p\) 的概率进入第 \(i\) 个房间，那么老是去抓第 \(i\) 个房间的概率为 \((1 - p) * a_i\) ，满足 \((1 - p) *a_i \le mid\) ，即：\(p \ge 1 - mid / a_i\) 对后者求和，如果小于 \(1\) ，就说明他还能使得被抓的人数变少。
code
#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const double eps = 1e-10;
int n , a[35];
double ans;
bool ck (double x) {
double ans = 0;
fu (i , 1 , n) {
if (a[i] > x) {
ans += 1 - x / (1.0 * a[i]);
}
}
if (ans > 1) return 1;
else return 0;
}
int main () {
freopen ("game.in" , "r" , stdin);
freopen ("game.out" , "w" , stdout);
scanf ("%d" , &n);
fu (i , 1 , n) scanf ("%d" , &a[i]);
double mid , l = 0 , r = 120;
while (r - l >= eps) {
mid = (l + r) * 0.5;
if (ck (mid)) l = mid;
else r = mid;
}
printf ("%.12f" , r);
return 0;
}