problem

有 n n n 個亂數生成器，第 i i i 個生成器可以均勻隨機地生成 [ L i , R i ] [L_i,R_i] [Li?,Ri?] 內的一個實數，

現在你要玩個游戲，從第 1 1 1 個生成器到第 n n n 個生成器，每次當前生成器會生成一個數，你需要選擇：

1. 相信魯迅，拿走這個數，游戲結束，
2. 相信魯迅，放棄這個數和這個生成器，使用下一個生成器（前提是下一個生成器必須存在），

求使用使得期望答案最大的策略時，期望答案是多少，

solution

observation：對于一個均勻隨機生成 [ L i , R i ] [L_i,R_i] [Li?,Ri?] 的生成器，生成數的期望為 L i + R i 2 \frac{L_i+R_i}{2} 2Li?+Ri??，

顯然，如果上一個生成器產生的期望為 x x x，下一個生成器產生數的期望 y y y，且 x < y x<y x<y，肯定是選擇下一個生成器，

更一般地，從后往前推，

設 f i : f_i: fi?: 從第 i i i 個生成器開始游戲得到的最大期望，

比較與 L i ? 1 , R i ? 1 L_{i-1},R_{i-1} Li?1?,Ri?1? 的大小關系，

• f i > R i ? 1 f_{i}>R_{i-1} fi?>Ri?1?，則 f i ? 1 = f i f_{i-1}=f_{i} fi?1?=fi?
• f i < L i ? 1 f_{i}<L_{i-1} fi?<Li?1?，則 f i ? 1 = L i ? 1 + R i ? 1 2 f_{i-1}=\frac{L_{i-1}+R_{i-1}}{2} fi?1?=2Li?1?+Ri?1??
• otherwise \text{otherwise} otherwise， k = f i ? L i ? 1 R i ? 1 ? L i ? 1 ? f i ? 1 = k ? f i + ( 1 ? k ) ? ( f i + R i ? 1 ) 2 k=\frac{f_{i}-L_{i-1}}{R_{i-1}-L_{i-1}}\Rightarrow f_{i-1}=k*f_{i}+(1-k)*\frac{(f_i+R_{i-1})}{2} k=Ri?1??Li?1?fi??Li?1???fi?1?=k?fi?+(1?k)?2(fi?+Ri?1?)?

計算方法就是加權平均，

code

#include <cstdio>
#include <iostream>
using namespace std;
#define double long double
#define maxn 1000005
#define eps 1e-7
int n;
double l[maxn], r[maxn], f[maxn];

int main() {
    freopen( "pag.in", "r", stdin );
    freopen( "pag.out", "w", stdout );
    scanf( "%d", &n );
    for( int i = 1;i <= n;i ++ ) scanf( "%Lf %Lf", &l[i], &r[i] );
    f[n] = ( l[n] + r[n] ) / 2;
    for( int i = n - 1;i;i -- ) {
        if( f[i + 1] - r[i] >= eps ) f[i] = f[i + 1];
        else if( f[i + 1] - l[i] >= eps ) {
            double k = ( f[i + 1] - l[i] ) / ( r[i] - l[i] );
            f[i] = k * f[i + 1] + ( 1 - k ) * ( r[i] + f[i + 1] ) / 2;
        }
        else f[i] = ( l[i] + r[i] ) / 2;
    }
    double ans = 0;
    for( int i = 1;i <= n;i ++ ) ans = max( ans, f[i] );
    printf( "%.5Lf\n", ans );
    return 0;
}