abc236 E - Average and Median

题意：

在给定数组中选数，要求任意相邻的两数至少选一个。问选出来的数的最大平均数和最大中位数

\(n\le 1e5, 1\le a_i\le 1e9\)

思路：

平均数、中位数的典中典二分+转化

this way: https://blog.csdn.net/Mr_dimple/article/details/122679274

const int N = 1e5 + 5;
int n, a[N];
void sol() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
{
    auto ok = [&](double x) {
        static double f[N]; f[1] = a[1] - x;
        for(int i = 2; i <= n; i++)
            f[i] = max(f[i - 1], f[i - 2]) + a[i] - x;
        return max(f[n], f[n - 1]) >= 0;
    };
    double l = 1, r = 1e9;
    int _ = 500; while(_--) { //实测40次也能AC
        double mid = (l + r) / 2;
        if(ok(mid)) l = mid; else r = mid;
    }
    cout << fixed << setprecision(9) << l << '\n';
}
{
    auto ok = [&](int x) {
        static int f[N]; f[1] = (a[1] >= x ? 1 : -1);
        for(int i = 2; i <= n; i++)
            f[i] = max(f[i - 1], f[i - 2]) + (a[i] >= x ? 1 : -1);
        return max(f[n], f[n - 1]) > 0;
    };
    int l = 1, r = 1e9;
    while(l < r) {
        int mid = l + (r - l + 1) / 2; //防爆int
        if(ok(mid)) l = mid; else r = mid - 1;
    }
    cout << l << '\n';
}
}