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; }