578C - Weakness and Poorness 三分

題意：

每個數都減x，找到合适的x，使得最大的abs(連續子序列的和)->最小

解法：

三分，類開口朝上的二次函數

執行個體代碼：

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <vector>
#define rep(i,n) for(i=0;i<n;i++)
#define cle(x) memset(x,0,sizeof(x))

#define ll long long
const int maxn=+;
using namespace std;
ll a[maxn];
long double b[maxn];
long double ans;
int n;
long double doit (long double x){
    for(int i=;i<=n;i++)b[i]=a[i];
    for(int i=;i<=n;i++)b[i]-=(x*i);
    long double mi=;
    long double ma=;
    long double re=;
    for(int i=;i<=n;i++){
        re=max(re,max(abs(b[i]-mi),abs(b[i]-ma)));
        mi=min(mi,b[i]);
        ma=max(ma,b[i]);
    }
    ans=min(ans,re);
    return re;
}
int main()
{
#ifndef ONLINE_JUDGE
     freopen("in.txt","r",stdin);
     //freopen("out.txt","w",stdout);
#endif
    while(cin>>n){
        int i;
        for(i=;i<=n;i++)scanf("%I64d",&a[i]);
        for(i=;i<=n;i++)a[i]=a[i-]+a[i];
        long double l=-,r=;
        int T=;
        ans=;
        while(T--){
            long double ml=l+(r-l)/;
            long double mr=r-(r-l)/;
            if(doit(ml)>doit(mr))l=ml;
            else r=mr;
        }
        printf("%.12lf\n",(double)ans);
    }
    return ;
}