首页 > 其他 > 详细

Andrey and Problem题解

时间:2019-11-11 21:07:16      阅读:90      评论:0      收藏:0      [点我收藏+]

Andrey and Problem题解

我们显然可以转化为:
找出某一种顺序,按此种顺序算概率,使概率最大:
对于一点i,之前答案为:ans,则现在答案为:\(ans*(1-p_{i})+p_{i}*\prod_{j=1}^{i-1}(1-p_{j})=ans+p_{i}*(\prod_{j=1}^{i-1}(1-p_{j})-ans)\)
\(ans\)\(\prod_{j=1}^{i-1}(1-p_{j})-ans\)都为定值,所以要使答案最大,即让\(p_i\)最大,按\(p_i\)从大到小排序即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+6;
const double eps=1e-8;
int n;
double p[N],mul=1.00,ans=0;
bool cmp(double u,double v){return u>v;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%lf",&p[i]);
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;++i){
        if(mul-ans>eps) ans=ans+p[i]*(mul-ans);
        else break;
        mul=mul*(1-p[i]);
    }
    printf("%.10lf",ans);
    return 0;
}

Andrey and Problem题解

原文:https://www.cnblogs.com/ljk123-de-bo-ke/p/11837950.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!