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

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

阅读量：4971 次

发布时间：2019-06-12

本文共 2449 字，大约阅读时间需要 8 分钟。

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

1 2 3

Sample Output

1.000000000000000

HINT

题意

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

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

题解：

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

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

感觉尺取法也行

代码：

//qscqesze#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   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-9int 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\n",check((l+r)/2.0));}