NOIP2023模拟12联测33 B. 游戏
文章目录
- NOIP2023模拟12联测33 B. 游戏
- 题目大意
- 思路
- code
题目大意
期望题
思路
二分答案 m i d mid mid ,我们只关注学生是否能够使得被抓的人数 ≤ m i d \le mid ≤mid
那我们就只关心 a > m i d a > mid a>mid 的房间就行了。
设学生有 p p p 的概率进入第 i i i 个房间,那么老是去抓第 i i i 个房间的概率为 ( 1 − p ) ∗ a i (1 - p) * a_i (1−p)∗ai ,满足 ( 1 − p ) ∗ a i ≤ m i d (1 - p) *a_i \le mid (1−p)∗ai≤mid ,即: p ≥ 1 − m i d / a i p \ge 1 - mid / a_i p≥1−mid/ai 对后者求和,如果小于 1 1 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;
}