[CF442B] Andrey and Problem

[CF442B] Andrey and Problem - 概率,贪心

Description

有 n 个炸弹，每个炸弹有成功率 pi，选出子集，要使得恰好 1 个炸弹爆炸的概率最大。

Solution

假设前面已经选了若干个人，答案为 x，且全失败概率为 f，则加入一个 pi=y，其答案会变为 x+y(f-x)

贪心，按成功率排序，如果 f-x>0 那么我们就给他加一个新的最大的 y，所以取出来的其实一定是一个后缀

现在相当于我们只需要检查每个后缀的答案即可

（证明没整明白）

#include <bits/stdc++.h>
using namespace std;

signed main()
{
    int n;
    cin >> n;
    vector<double> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    double x = 0, f = 1, ans = 0;
    for (int i = 0; i < n; i++)
    {
        double y = a[i];
        x = x * (1 - y) + y * f;
        f *= 1 - y;
        ans = max(ans, x);
    }
    cout << fixed << setprecision(12) << ans;
}