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.
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 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.
3
1 2 3
1.000000000000000
4
1 2 3 4
2.000000000000000
10
1 10 2 9 3 8 4 7 5 6
4.500000000000000
For the first case, the optimal value of x is 2 so the sequence becomes - 1, 0, 1 and the max poorness occurs at the segment "-1" or segment "1". The poorness value (answer) equals to 1 in this case.
For the second sample the optimal value of x is 2.5 so the sequence becomes - 1.5, - 0.5, 0.5, 1.5 and the max poorness occurs on segment "-1.5 -0.5" or "0.5 1.5". The poorness value (answer) equals to 2 in this case.
题意: 给你一段序列a1, a2, ..., an
a1 - x, a2 - x, ..., an - x. 对于每一个x 都有ans=连续子序列的和的绝对值的最大值
输出min(ans)
题解: 贪心求出连续子序列的和的绝对值的最大值 o(n)处理
三分x (x为实数存在负数) 求min(ans)
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 using namespace std; 6 int n; 7 double a[200005]; 8 double fun(double x) 9 { 10 double sum1=0.0,sum2=0.0; 11 double max1=0.0,min1=100005.0; 12 for(int i=1;i<=n;i++) 13 { 14 if((sum1+a[i]-x)<0) 15 sum1=0; 16 else 17 sum1=sum1+a[i]-x; 18 if((sum2+a[i]-x)>0) 19 sum2=0; 20 else 21 sum2=sum2+a[i]-x; 22 max1=max(max1,sum1); 23 min1=min(min1,sum2); 24 } 25 return max(abs(max1),abs(min1)); 26 } 27 int main() 28 { 29 scanf("%d",&n); 30 for(int i=1;i<=n;i++) 31 scanf("%lf",&a[i]); 32 double l=-1e9,r=1e9,m1=0.0,m2=0.0; 33 for(int i=0;i<600;i++) 34 { 35 m1=l+(r-l)/3.0; 36 m2=r-(r-l)/3.0; 37 if(fun(m1)<fun(m2)) 38 r=m2; 39 else 40 l=m1; 41 } 42 printf("%f ",fun(l)); 43 return 0; 44 }