[USACO19FEB]Cow Dating P

题目链接：https://www.luogu.com.cn/problem/P5242

这是一道很妙的概率贪心题
首先我们应该列出选择$L$到$R$这个区间的概率的公式：
令$P={\prod }_{i=l}^{r}1?p[i]$
则:$p_{l,r}={\sum }_{i=l}^{r}P?\frac{p[i]}{1?p[i]}$

那么我们看到数据范围，贪心是肯定少不了了
考虑$p_{l,r+1}$比$p_{l,r}$大的情况

$$p_{l,r}=\sum _{i=l}^{r}P?\frac{p[i]}{1?p[i]}<p_{l,r+1}=\sum _{i=l}^{r+1}P?\frac{p[i]}{1?p[i]}$$

移项化简后，我们发现这一条件等价于${\sum }_{i=l}^r\frac{p[i]}{1?p[i]}<1$

而且$\frac{p[i]}{1?p[i]}$恒为正数
也就是说，我们可以先选定一个点作为左端点，然后不断向右$interval$，直到上述条件不满足为止

这样就有两种做法，第一种枚举每个左端点再二分，第二种双指针
显然双指针更优，时间复杂度$O(N)$

$Code$

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
#define max(a, b) a > b? a : b
const int S = 1 << 21;
char p0[S],*p1,*p2;
#define getchar() (p2 == p1 && (p2 = (p1 = p0) + fread(p0,1,S,stdin)) == p1 ? EOF : *p1++)
const int MAXN = 1e6;
double p[MAXN + 10];
inline int read();int main(){
    freopen ("std.in", "r", stdin);freopen ("std.out", "w", stdout);int n = read();for (register int i = 1; i <= n; ++i){
    int x = read();p[i] = (double)x / 1e6;}int l = 1;double tmp1 = p[1], tmp2 = p[1] / (1 - p[1]), s = 1 - p[1], ans = 0;for (register int i = 2; i <= n; ++i){
    if (tmp2 > 1){
    ans = max(ans, tmp1);while (tmp2 > 1){
    tmp2 -= p[l] / (1 - p[l]);s /= 1 - p[l];tmp1 = (tmp1 - p[l] * s) / (1 - p[l]);ans = max(ans, tmp1);++l;}}tmp2 += p[i] / (1 - p[i]);tmp1 = tmp1 * (1 - p[i]) + p[i] * s;s *= 1 - p[i];ans = max(ans, tmp1);}cout << (int)(ans * 1e6) << endl;return 0;
}inline int read(){
    int x = 0;char c = getchar();while (!isdigit(c))c = getchar();while (isdigit(c))x = (x << 1) + (x << 3) + (c & 15), c = getchar();return x;
}