cf578 C. Weakness and Poorness（三分、最大子段和）

题意：

子段的价值定义为子段和的绝对值。数组的价值定义为最大子段价值。

把给定整数组中的所有数减去一个实数x，最小化数组的价值。

\(n\le 2e5, |a_i|\le 1e4\)

思路：

数组的价值关于x是单峰下凸的。在 \([-1e4,1e4]\) 中三分x即可。线性求最大字段和是经典贪心了。

注意浮点数三分要限制次数而非eps！实测eps取1e-11会wa，取1e-12又会tle，实在难绷。次数的话，取100次或200次左右都行。

const signed N = 2e5 + 3;
int n, a[N];

db f(db x)
{
    db m1 = 0, m2 = 0, s1 = 0, s2 = 0;
    for(int i = 1; i <= n; i++)
        s1=max(s1,0.0)+(db)a[i]-x, m1 = max(m1, s1),
        s2=min(s2,0.0)+(db)a[i]-x, m2 = min(m2, s2);
    return max(m1, -m2);
}

signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    db l = -1e4, r = 1e4;
    int m = 100; while(m--)
    {
        db lm = l + (r - l) / 3;
        db rm = r - (r - l) / 3;
        if(f(lm) < f(rm)) r = rm;
        else l = lm;
    }
    cout << fixed << setprecision(7) << f(l);
}