0w1

CF 579E Weakness and Poorness ( Binary Search )

Problem - E - Codeforces
We are to find x that will give minimum for max{ ABS( SUM( a[ k ] - x Ɐ i ≤ k ≤ j ) ) Ɐ 1 ≤ i ≤ j ≤ n }.
Let us first remove absolute and get
max{ max{ SUM( a[ k ] - x Ɐ i ≤ k ≤ j ) Ɐ 1 ≤ i ≤ j ≤ n }, max{ - SUM( a[ k ] - x Ɐ i ≤ k ≤ j ) Ɐ 1 ≤ i ≤ j ≤ n } }
We will find that the former is a strictly decreasing function, and the latter is a strictly increasing function. Thus we will apply a binary search to find the intersection, which is the trough.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXABSA = 1e4;

int n;
double a[MAXN];

double pos, neg;
double t[MAXN];
bool calc(double x){
    pos = neg = 0.0;

    for(int i = 0; i < n; ++i)
        t[i] = a[i] - x;

    double sum = 0.0;
    for(int i = 0; i < n; ++i){ // dp method to find maximum sum in consecutive subsequence O( n )
        sum += t[i];
        if( sum > pos ) pos = sum;
        if( sum < 0.0 ) sum = 0.0;
    }

    for(int i = 0; i < n; ++i)
        t[i] = -t[i];

    sum = 0.0;
    for(int i = 0; i < n; ++i){
        sum += t[i];
        if( sum > neg ) neg = sum;
        if( sum < 0.0 ) sum = 0.0;
    }

    return pos > neg;
}

void solve(){
    double lb = *min_element( a, a + n );
    double ub = *max_element( a, a + n );
    for(int i = 0; i < 100; ++i){
        double mid = ( lb + ub ) / 2.0;
        if( calc( mid ) ) lb = mid; // pos is bigger = x is too small 
        else ub = mid;
    }
    printf("%.7lf\n", max<double>( pos, neg ));
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%lf", &a[i]);
    solve();
    return 0;
}