由于目前可供奶牛们使用的约会网站并没有给Farmer John留下深刻印象，他决定推出一个基于新匹配算法的奶牛交友网站，该算法可基于公牛和母牛间的共同兴趣对公牛和母牛进行匹配。
Bessie在寻找情人节Barn Dance的合作伙伴时，决定试用这个网站。在注册账户之后，FJ的算法为他给出了一个长度为 N(1≤N≤1e6) 的匹配列表，列表上每头公牛接受她舞蹈邀请的概率为 p (0 < p < 1)。
Bessie决定向列表中的一个连续区间内的奶牛发送邀请，但Bessie希望恰好只有一个奶牛接受邀请。请帮助Bessie求出恰好只有一个奶牛接受邀请的最大概率是多少。
令 pi ? 表示第i个位置是1的概率，那么1~i 这 i 个数都不选的概率 si ?= ∏ik=1? (1−pk?) , 1~i 中只选 i 这个数的概率为 si * ti? ( ti?=∑ik=1 (1−pk) / ?pk??)
那么显然把只选区间 [ l, r ] 中一个数的答案加起来得区间的答案为? sr/sl-1? ?(tr?−tl−1?)
固定右端点r，直观感觉到随着l的左移，乘积第二项变大，乘积第一项变小。
那么总的答案为 (1-p1)(1-p2)..(1-pn) * ( p1/(1-p1) + p2/(1-p2) + ... + pn/(1-pn) )
我们可以发现，右端点的取值是单调递增的
于是，我们可以极限一下，用一个双指针法，类似于队列。
记录两个变量，表示和 与 积即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int MAXN=1e6+10; 4 typedef long double ld; 5 6 int n; 7 ld a[MAXN],ans,pro,sum; 8 inline int read(){ 9 int x=0,f=1;char ch=getchar(); 10 while(ch<‘0‘||ch>‘9‘){ 11 if(ch==‘-‘) f=-1; 12 ch=getchar(); 13 } 14 while(ch>=‘0‘&&ch<=‘9‘){ 15 x=x*10+ch-48; 16 ch=getchar(); 17 } 18 return x*f; 19 } 20 21 int main(){ 22 n=read(); 23 for(int i=1;i<=n;++i){ 24 a[i]=(ld)read(); 25 a[i]/=1e6; 26 ans=max(ans,a[i]); 27 } 28 pro=1;sum=0; 29 int j=1;//i,j双指针。i左j右 30 for(int i=1;i<=n;++i){ 31 while(j<=n&&pro*sum<pro*(1-a[j])*(sum+a[j]/(1-a[j]))){ 32 pro*=(1-a[j]); 33 sum+=a[j]/(1-a[j]); 34 ++j; 35 } 36 //cout<<i<<‘ ‘<<j<<endl; 37 ans=max(ans,pro*sum); 38 pro/=(1-a[i]); 39 sum-=a[i]/(1-a[i]); 40 } 41 printf("%d\n",(int)(ans*1e6)); 42 return 0; 43 }
USACO 2019 February Contest Platinum T1: Cow Dating
原文：https://www.cnblogs.com/LI-dox/p/11223748.html