Andrey and Problem

Created by LXC on Thu Apr 27 14:02:19 2023

https://codeforces.com/problemset/problem/442/B

ranting: 1800

tag: greedy, math, probabilities

题意

给出一个长度为n的浮点数数组a。数组每个值在0到1之间。

现在你要n个人出题。

第i个人出题成功的概率为a[i]

如果可以从n个人中选一些人出题，恰好只有一个人出题的最大概率是多少？

题解

假设选了k个人那么恰好有一人成功的概率是：
$\sum \limits_{i=1}^{k} \prod \limits_{j \neq i} (1-a_j)$和式变换，分离变量后
$ \sum \limits_{i=1}^{k} \frac{a_i}{1-a_i} \prod \limits_{j=1}^{k} (1-a_j)$

令$S=\sum \limits_{i=1}^{k} \frac{a_i}{1-a_i}, P = \prod \limits_{j=1}^{k} (1-a_j)$

如果我们新增一个人u，概率的变化为$(S+\frac{a_u}{1-a_u})(P(1-a_u)) - S\cdot P = P\cdot a_u (1-S)$

由此我们看出，新增一个人u不能决定概率的增长，而是由前k个人的S所决定，若S<1则概率会增长。而对于u只能决定增长概率的大小，若$a_u$越大则增长的概率越大。

因此，可以采取贪心的策略解决这个问题：

我们将概率进行排序。每次选择概率最大的，并计算S和P，当S大于1时则停止增加；当S不大于1时，概率是不会减少的，所以可以继续增加人数。由于$a_i$越大的人增长的概率会越大。我们优先选择概率大的。

因此在升序排序后的a中求最长使得S<=1的后缀，并计算该后缀的P，答案就是PS。

这样为什么是正确的呢？
可以用反证法。如果最后成功概率最大时选了k个人，那么一定是a中最大的k个。试想如果u是a中最大的k个中的某一个，而最后选取的k个人中没有一个是u。由于任意k-1个人的S是不大于1的，根据前面公式，这个k人中概率最小的可以替换为u，让最终成功概率更大。

代码

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 1005
#define MOD 998244353
using namespace std;

/*

prod((1-a[i])) sum(a[i]/(1-a[i]))

*/

double a[N];

void sol() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    if (a[n - 1] == 1) {
        cout << "1\n";
        return;
    }
    double P = 1, S = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (S > 1)
            break;
        S += a[i] / (1 - a[i]);
        P *= (1 - a[i]);
    }
    cout.precision(12);
    cout << P * S << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}