Codeforces 442B Andrey and Problem(貪心)

題目鏈接：Codeforces 442B Andrey and Problem

題目大意：Andrey有一個問題，想要朋友們為自己出一道題，現在他有n個朋友，每個朋友想出題目的概率為pi,但是他可以同時向多個人尋求幫助，不過他只能要一道題，也就是如果他向兩個人尋求幫助，如果兩個人都成功出題，也是不可以的。

解題思路：貪心，從概率最大的人開始考慮，如果詢問他使得概率變大，則要詢問。

#include 
#include 
#include 

using namespace std;
const int N = 105;
const double eps = 1e-9;

int n, c, rec[N];
double s, p[N];

double solve (int x) {
    double ans = s * p[x];
    double tmp = s * (1-p[x]);

    for (int i = 0; i < c; i++)
        ans += tmp / (1-p[rec[i]]) * p[rec[i]];
    return ans;
}

int main () {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%lf", &p[i]);

    sort (p, p + n);

    c = 0;
    double ans = p[n-1];
    s = 1 - p[n-1];
    rec[c++] = n-1;

    for (int i = n-2; i >= 0; i--) {
        double tmp = solve(i);

        if (tmp > ans) {
            ans = tmp;
            rec[c++] = i;
            s *= (1 - p[i]);
        }
    }

    printf("%.12lf\n", ans);
    return 0;
}