题目链接
题意分析
首先我们可以得出计算公式
\[s_i=\prod_{k=1}^i(1-p_k)
\]
\[f_i=\sum_{k=1}^i\frac{p_k}{1-p_k}
\]
那么
\[ans(i,j)=\frac{s_r}{s_{l-1}}{f_r-f_{l-1}}
\]
强行枚举 \(O(n^2)\)
我们冷机观察一波发现 可以使用尺取法
然后优化成了\(O(n)\)
CODE:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define N 500008
#define IL inline
#define M 1008611
#define D long double
#define R register
using namespace std;
template<typename T>IL void read(T &_)
{
T __=0,___=1;char ____=getchar();
while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
_=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
int n;
D num[M],cdy=1.0,wzy,ans;
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n);
for(R int i=1,x;i<=n;++i)
{
read(x);
num[i]=((D)x/1000000.0);
ans=max(ans,num[i]);
}
for(R int i=1,tail=1;i<=n;++i)
{
while(tail<=n&&cdy*wzy<cdy*(1.0-num[tail])*(wzy+num[tail]/(1.0-num[tail])))
{
cdy*=(1.0-num[tail]);
wzy+=num[tail]/(1.0-num[tail]);
++tail;
}
ans=max(ans,cdy*wzy);
cdy/=(1.0-num[i]);wzy-=num[i]/(1.0-num[i]);
}
printf("%d\n",(int)(ans*1000000));
// fclose(stdin);
// fclose(stdout);
return 0;
}