Codeforces 442B Andrey and Problem(贪心)

本文主要是介绍Codeforces 442B Andrey and Problem(贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：Codeforces 442B Andrey and Problem

题目大意：Andrey有一个问题，想要朋友们为自己出一道题，现在他有n个朋友，每个朋友想出题目的概率为pi,但是他可以同时向多个人寻求帮助，不过他只能要一道题，也就是如果他向两个人寻求帮助，如果两个人都成功出题，也是不可以的。

解题思路：贪心，从概率最大的人开始考虑，如果询问他使得概率变大，则要询问。

#include <cstdio>
#include <cstring>
#include <algorithm>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;
}

这篇关于Codeforces 442B Andrey and Problem(贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---