首页 > 代码库 > cf442 B.Andrey and Problem

cf442 B.Andrey and Problem

看题偷瞄到题解2333(以为是劲题呢。。结果是乱贪心,奇怪)

排序之后,如果加入下一个比现在更优就更新答案(奇怪啊)

t=ans*(1-a[i])+s*a[i];(ans*(1-a[i])是新的一位不选的概率(即到这位之前已经选好)+选这位(即s*a[i])(s是以前都不选的概率))

 1 #include<bits/stdc++.h>
 2 #define LL long long
 3 #define LD long double  
 4 #define  N 100005
 5 using namespace std;
 6 inline int ra()
 7 {
 8     int x=0,f=1; char ch=getchar();
 9     while (ch<0 || ch>9) {if (ch==-) f=-1; ch=getchar();}
10     while (ch>=0 && ch<=9) {x=x*10+ch-0; ch=getchar();}
11     return x*f;
12 }
13 double ans,s,a[N];
14 int main()
15 {
16     int n=ra();
17     for (int i=1; i<=n; i++)
18         scanf("%lf",&a[i]);
19     sort(a+1,a+n+1);
20     s=1-a[n]; ans=a[n];
21     for (int i=n-1; i>=1; i--)
22     {
23         double t=ans*(1-a[i])+s*a[i];
24         if (t>ans) ans=t;
25         else break;
26         s*=(1-a[i]);
27     }
28     printf("%.12lf",ans);
29     return 0;
30 }

 

cf442 B.Andrey and Problem