题目链接: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 1105B - Zuhair and Strings 测试点37个(全)
Codeforces - 1107B. Digital root & 1107C. Brutality(规律 & 贪心)Codeforces - 1107B.
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
Codeforces - 1131C. Birthday(贪心)题目链接题目给你n和n个数,要你重新排列n个数,使得这些数的相邻差值中最大的那个值最小。stat
Codeforces-Problem-Set
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
Codeforces部门2,A # And a2oj Ladder 4 some problems Ladder URL:http://a2oj.com/Ladder.jsp?ID=4难度等级:2问题提示: 1- 4A....... http://codeforc
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 185A - Plant 全测试点49个
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
题目大意:给出 n 个数字组成的序列,现在可以对数列进行多次操作,每次操作可以选择其中一段连续的数列,用其平均数替换原位置,换句话说,若原连续数列为 1 2 3,则可以替换为 2 2 2,问如何操作可以使得最后答案...
Codeforces-problem-solution
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...
语言:English Codeforces问题跟踪器Chrome扩展程序可帮助您跟踪问题。 chrome扩展程序可帮助您跟踪代码部队问题。