Codeforces E. Weakness and Poorness（三分最大子列和）

大子列和）"/>

Codeforces E. Weakness and Poorness（三分最大子列和）

题目描述：

E. 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, ..., *a**n*.

Determine a real number x such that the weakness of the sequence a1 - x, a2 - 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 a1, a2, ..., *a**n* (|*a**i*| ≤ 10 000).

Output

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

Examples

Input

Copy

31 2 3

Output

Copy

1.000000000000000

Input

Copy

41 2 3 4

Output

Copy

2.000000000000000

Input

Copy

101 10 2 9 3 8 4 7 5 6

Output

Copy

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\)后的子列和的绝对值最大(poorness)的情况下的可能的最小值(weakness)。（有点绕哈?）

从样例可以看出当x很小时weakness会很大，随着x的增大weakness渐渐减小，最后又增大，这不是一个单调问题，所以用三分，x就从\(-10^4\)枚举到\(10^4\)，找出weakness最小时的\(x\)就行了。

所以现在要求子列和，这个可以求，参见上篇博客，关键时还要求绝对值的最大值。有两种可能：如果最大子列和是正的，那么最大的子列和绝对值就是它，也有可能当求出来是个负数时的子列和的绝对值最大，就把数列所有数去反后再求一次最大值，去反后刚才是正的就变成负的了，在新一次的求最大子列和中会忽视掉他，相当于求子列和为负时的最小值。取两者的最大值就是weakness。

注意三分的精度选择：3e-12我WA了，2e-12我过了，1e-12我TEL了。

代码：

#include <iostream>
#include <iomanip>
#define max_n 200005
using namespace std;
int n;
double a[max_n];
double b[max_n];
double x;
double maxsum(double A[]) {double ans = 0, tmp = 0;for(int i = 1; i <= n; i++) {tmp += A[i];if(tmp < 0) tmp = 0;ans = max(ans, tmp);}return ans;
}
double maxsum_1(double* num)
{double lmin = 0;num[0] = 0;double ans = num[1];double t = 0;for(int i = 2;i<=n+1;i++){//cout << "ans " << ans << endl;//cout << "lmin " << lmin << endl;t += num[i-1];//cout << "t " << t << endl;//cout << " num " << num[i] << endl;if(t-lmin>ans)//更新最大值{ans = t-lmin;}if(lmin>t){lmin = t;}}return ans;
}
double f(double a[],double x)
{for(int i = 1;i<=n;i++){b[i] = a[i]-x;}double ans1 = maxsum(b);for(int i = 1;i<=n;i++){b[i] = -b[i];}double ans2 = maxsum(b);double ans = max(ans1,ans2);return ans;
}
double search()
{double left = -1e4;double right = 1e4;double mid,mmid;while(right-left>2e-12){//cout << "left " << left << endl;//cout << "right " << right << endl;mid = (2*left+right)/3.0;mmid = (2*mid+right)/3.0;double ans1 = f(a,mid);double ans2 = f(a,mmid);if(ans1<ans2){right = mmid;}else{left = mid;}}return f(a,right);
}
int main()
{cin >> n;for(int i = 1;i<=n;i++){cin >> a[i];}cout.setf(ios_base::fixed,ios_base::floatfield);cout << setprecision(15) << search() << endl;return 0;
}

参考文章：

HelloWorld10086，CodeForces 578C Weakness and Poorness（三分法+最大子段和），

转载于:.html