cf 320# Weakness and Poorness(三分+最大连续和)

cf 320# Weakness and Poorness(三分+最大连续和)"/>

cf 320# Weakness and Poorness(三分+最大连续和)

题目：

题意：给定n个数，找一个实数x，然后n个数都减去x，使得ans=max(|最小连续和|，|最大连续和|)最小。求ans。

分析：啊，印象中的第一个三分。|最大连续和|与x逆增长，|最小连续和|与x正增长，形成抛物线，三分x就行了。
代码：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 2e5+6;
double a[maxn];
double cal(int n)
{double ret1=0,temp=0;for(int i=1;i<=n;i++){if(temp>0)temp+=a[i];elsetemp=a[i];if(temp>ret1)ret1=temp;a[i]=-a[i];}double ret2=0;temp=0;for(int i=1;i<=n;i++){if(temp>0)temp+=a[i];elsetemp=a[i];a[i]=-a[i];if(temp>ret2)ret2=temp;}return max(ret1,ret2);
}void pro(int n,double x)
{for(int i=1;i<=n;i++)a[i]-=x;
}double Find(int n)
{double down=-10000.0,mid,midmid,up=10000.0,ret=1e18;for(int i=1;i<=500;i++){mid=(down+up)/2.0;midmid=(mid+up)/2.0;pro(n,mid);double temp1=cal(n);pro(n,-mid);pro(n,midmid);double temp2=cal(n);pro(n,-midmid);if(temp1<temp2)up=midmid;elsedown=mid;ret=min(ret,temp1);ret=min(ret,temp2);}return ret;
}int main()
{int n,i,j;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%lf",&a[i]);printf("%.12lf\n",Find(n));return 0;
}
/*int main()
{int n,i,j;double x,mx,mn;while(scanf("%d",&n)!=EOF){mx=-1e9;mn=1e9;for(i=1;i<=n;i++){scanf("%lf",&a[i]);if(a[i]>mx)mx=a[i];if(a[i]<mn)mn=a[i];}for(double i=mn;i<=mx;i+=0.1){pro(n,i);printf("%lf\n",cal(n));pro(n,-i);}}return 0;
}
*/