Codeforces 578.C Weakness and Poorness

Codeforces 578.C Weakness and Poorness"/>

Codeforces 578.C Weakness and Poorness

C. Weakness and Poorness time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

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.

Examples input

3
1 2 3

output

1.000000000000000

input

4
1 2 3 4

output

2.000000000000000

input

10
1 10 2 9 3 8 4 7 5 6

output

4.500000000000000

Note

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.

题目大意：找到一个x,使得原序列中的所有数减掉x后的最大的子段和的绝对值最小.

分析：因为最后的答案是一个浮点数，肯定不能用搜索枚举之类的方法做出来.题目中出现两个最值，想到要用二分.答案会随着x的增大减小而波动.不是二分，我也想不出好的数学式子来表示答案，只能三分法了.其实稍微分析一下发现真的满足单峰性.当x足够大时，所有的数都变成负数，x越大答案越大.当x足够小时所有的数都变成正数，x越小答案越小，所以这是一个向下凸的单峰函数.三分即可.

          求最大的字段和的绝对值可以先求出一开始的序列的(答案为正的)，然后将序列中的所有数取反，再来一次，两个答案取max.

          注意精度问题.允许误差6位.(一开始没看到一直TLE......).

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;int n;
double a[200010],ans,b[200010],c[200010],eps = 3e-12,sum1[200010],sum2[200010];double C(double x)
{double max1 = -100000.0,max2 = -100000.0;sum1[0] = sum2[0] = 0.0;for (int i = 1; i <= n; i++){b[i] = a[i] - x;c[i] = -b[i];}for (int i = 1; i <= n; i++){sum1[i] = max(sum1[i - 1] + b[i],b[i]);max1 = max(max1,sum1[i]);sum2[i] = max(sum2[i - 1] + c[i],c[i]);max2 = max(max2,sum2[i]);}return max(max1,max2);
}int main()
{scanf("%d",&n);for (int i = 1; i <= n; i++)scanf("%lf",&a[i]);if (n == 1)printf("%.15lf\n",0);else{double L = -20000.0,R = 20000.0;while (R - L > eps){double mid1 = L + (R - L) / 3.0,mid2 = R - (R - L) / 3.0;if (C(mid1) < C(mid2)){ans = mid1;R = mid2;}else{ans = mid2;L = mid1;}}printf("%.15lf\n",C(ans));}return 0;
}

 

转载于:.html