【Codeforces 442B】Andrey and Problem

题目传送门：http://codeforces.com/contest/442/problem/B
官方题解：http://codeforces.com/blog/entry/12739

此题真的是妙啊！ 奥妙重重.jpg
考虑当前已经有一个集合了，不失望的概率是f,设g=Π（1-其中所有人的p）
如果考虑是否加入第i个人，不难得出必须满足一下等式：
\(f \cdot (1 – p) + g \cdot p > f\)
化简得到，如果有优化的可能，则 g > f
然后来比较人选i和人选j
如果i优于j，则有以下不等式：
\(f \cdot (1 – {p_i}) + g \cdot {p_i} > f \cdot (1 – {p_j}) + g \cdot {p_j}\)
化简得到\({p_i} > {p_j}\)
又因为加入顺序明显不影响答案，所以排序之后从大到小贪心即可

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdio>
#include<cmath>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 100+9;
const double EPS = 1e-8;

int n;
double p[N],f,g=1;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

int main(){
	n = read(); for (int i=1;i<=n;i++) scanf("%lf",&p[i]);
	sort(p+1,p+1+n); if (abs(p[n]-1) < EPS) {cout<<1; exit(0);}
	for (int i=n;i;i--) {
		double tmp = f*(1-p[i]) + g*p[i];
		if (tmp > f) f = tmp, g *= (1-p[i]);
		else break;
	} printf("%.10lf",f);
	return 0;
}