[CF578C] Weakness and Poorness

[CF578C] Weakness and Poorness - 三分

Description

给定一个长度为n的数组ai，求一个实数x，使得序列a1-x,a2-x,...,an-x的所有连续子序列的位置的和的绝对值的最大值最小。

Solution

max 运算可以保持函数的凸性，因此最终的结果关于 x 是凸的，直接三分即可

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6 + 5;
int n;
int a[N];

double f(double x)
{
    double ans = 0, sum = 0;
    for (int i = 1; i <= n; i++)
    {
        sum += a[i] - x;
        ans = max(ans, abs(sum));
        sum = max(sum, 0.0);
    }
    sum = 0;
    for (int i = 1; i <= n; i++)
    {
        sum += a[i] - x;
        ans = max(ans, abs(sum));
        sum = min(sum, 0.0);
    }
    return ans;
}

signed main()
{
    ios::sync_with_stdio(false);

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

    double l = -1e4, r = 1e4;

    for (int i = 1; i <= 300; i++)
    {
        double ml = (l * 2 + r) / 3, mr = (l + r * 2) / 3;
        if (f(ml) < f(mr))
            r = mr;
        else
            l = ml;
    }

    cout << fixed << setprecision(10) << f(l) << endl;
}