Weakness and Poorness(Codeforces Round #320)"/>
578C. Weakness and Poorness(Codeforces Round #320)
C. Weakness and Poorness time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard outputYou 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.
InputThe 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).
OutputOutput 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 test(s) input3 1 2 3output
1.000000000000000input
4 1 2 3 4output
2.000000000000000input
10 1 10 2 9 3 8 4 7 5 6output
4.500000000000000Note
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后的最大连续子序列和最小连续子序列是呈现单谷函数的,可以用三分来做,
至于最大连续子序列和最小连续子序列的求法,只要2遍最大连续和就可以了,第1遍后将每个数取反,这样第2
遍也是一个最大连续和。
还有一种方法是二分,随着x的递增,序列的最大连续子序列和肯定在减小,因为每个数都减小了,其最小连
续子序列和的绝对值肯定是增大趋势,都是单调的,于是将最大连续子序列的和和最小连续子序列和的绝对值分开记录,就可二分,会有点麻烦。
ps:被精度坑了,1e-11会wa,1e-12会T,三分100次就过了,通过这次学到了浮点三分根据数据通过控制三分次数更好。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const double eps=1e-11;
const int maxn=200000+100;
int a[maxn];
double l[maxn];
int n;
double cal(double x)
{double sum=0;for(int i=0;i<n;i++)l[i]=a[i]*1.0-x;double cur=0;for(int i=0;i<n;i++){cur=cur+l[i];if(cur<0)cur=0;sum=max(sum,cur);l[i]=-l[i];}cur=0;for(int i=0;i<n;i++){cur=cur+l[i];if(cur<0)cur=0;sum=max(sum,cur);}return sum;
}
int main()
{scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);}double l=-1e4,r=1e4,m1,m2,v1,v2;int t=100;while(t--){m1=l+(r-l)/3;m2=r-(r-l)/3;v1=cal(m1);v2=cal(m2);if(v1>v2)l=m1;else r=m2;}printf("%.15f\n",cal(l));return 0;
}
更多推荐
578C. Weakness and Poorness(Codeforces Round #320)
发布评论