题目链接

题意分析

首先我们可以得出计算公式

\[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; }