Weakness and Poorness CodeForces

Weakness and Poorness CodeForces"/>

Weakness and Poorness CodeForces

You are given a sequence of n integers a₁, a₂, ..., a_n.

Determine a real number x such that the weakness of the sequence a₁ - x, a₂ - x, ..., a_n - 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 a₁, a₂, ..., a_n (|a_i| ≤ 10 000).

Output

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

Example

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

Note

For the first case, the optimal value of x is 2 so the sequence becomes  - 1, 0, 1and 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.

#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
#define MAXN 200009
#define eps 1e-11 + 1e-12/2
typedef long long LL;using namespace std;
/*
要求a[i]减去某个数字x后的最大字段和的最小绝对值！
s(a[i]-x)是单调的，加上绝对值之后变成单谷函数，三分搜索
*/int n;
double a[MAXN],tmp[MAXN];
double cal(double x)
{for (int i = 0; i < n; i++)tmp[i] = a[i] - x;double cur = 0, ans = 0;for (int i = 0; i < n; i++){cur = cur + tmp[i];if (cur < 0)cur = 0;ans = max(cur, ans);}cur = 0;for (int i = 0; i < n; i++){cur = cur - tmp[i];if (cur < 0)cur = 0;ans = max(cur, ans);}return ans;
}
int main()
{scanf("%d", &n);for (int i = 0; i < n; i++)scanf("%lf", &a[i]);double beg = -10005, end = 10005;int time = 100;while (time--){double ml = (beg + beg + end) / 3, mr = (end + end + beg) / 3;if (cal(ml) > cal(mr))beg = ml;elseend = mr;}printf("%.15lf\n", cal(beg));return 0;
}

转载于:.html