公司网站未备案,智能建站系统开发,网站建设推广公司哪家好,网站建设策划实施要素NOIP2023模拟12联测33 B. 游戏 文章目录 NOIP2023模拟12联测33 B. 游戏题目大意思路code 题目大意 期望题
思路
二分答案 m i d mid mid #xff0c;我们只关注学生是否能够使得被抓的人数 ≤ m i d \le mid ≤mid
那我们就只关心 a m i d a mid amid 的房…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 amid 的房间就行了。
设学生有 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;
}
