Codeforces Round #320 (Div. 1) [Bayan Thanks-Round] C. Weakness and Poorness 三分 dp

C. Weakness and Poorness

Time Limit: 1 Sec  

Memory Limit: 256 MB

题目连接

http://codeforces.com/contest/578/problem/C

Description

You are given a sequence of n integers a1, a2, ..., an.

Determine a real number x such that the weakness of the sequence a1 - x, a2 - x, ..., an - x is as small as possible.

The weakness of a sequence is defined as the maximum value of the poorness over all segments (contiguous subsequences) of a sequence.

The poorness of a segment is defined as the absolute value of sum of the elements of segment.

Input

The first line contains one integer n (1 ≤ n ≤ 200 000), the length of a sequence.

The second line contains n integers a1, a2, ..., an (|ai| ≤ 10 000).

Output

Output a real number denoting the minimum possible weakness of a1 - x, a2 - x, ..., an - x. Your answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6

Sample Input

3
1 2 3

Sample Output

1.000000000000000

HINT

题意

给你n个数之后，让这n个数都减去一个x后

使得这n个数中的某个线段，的连续和的绝对值的最大值最小

题解：

这个是一个凸性的函数，符合三分

于是就三分咯，check是用一个dp来check，是on的

感觉尺取法也行

代码：

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 2000000 + 500
#define mod 10007
#define eps 1e-9
int Num;
char CH[20];
//const int inf=0x7fffffff;   //нчоч╢С
const int inf=0x3f3f3f3f;
/*

inline void P(int x)
{
    Num=0;if(!x){putchar('0');puts("");return;}
    while(x>0)CH[++Num]=x%10,x/=10;
    while(Num)putchar(CH[Num--]+48);
    puts("");
}
*/
//**************************************************************************************
double a[200220];
double g[200220];
int n;
double r,l,mid1,mid2;
double check(double mid)
{
    double q1=0,q2=0,q3=0;
    for(int i=1;i<=n;i++)
        g[i]=a[i]-mid;
    for(int i=1;i<=n;i++)
        q1=max(g[i],g[i]+q1),q3=max(q3,q1);
    for(int i=1;i<=n;i++)
        g[i]=g[i]*(-1.0);
    for(int i=1;i<=n;i++)
        q2=max(g[i],g[i]+q2),q3=max(q3,q2);
    return q3;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%lf",&a[i]);
    r = 30000.0;l = -30000.0;
    while(r-l>1e-11)
    {
        double mid1=(l+l+r)/3.0;
        double mid2=(l+r+r)/3.0;
        if(check(mid1)>=check(mid2))
            l = mid1;
        else
            r = mid2;
    }
    printf("%.13lf
",check((l+r)/2.0));
}