cf#320 Div.2 Problem E Weakness and Poorness

Div.2 Problem E Weakness and Poorness"/>

cf#320 Div.2 Problem E Weakness and Poorness

这题的代码是参考比赛中大神的AC代码的，据说用到了三分思想和前缀和，这里先记下来，日后再消化

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int N;
int A[200005];
double f(double x){double res=0,s1=0,s2=0;for(int i=0;i<N;i++){if(s1<0)s1=A[i]-x;else s1+=A[i]-x;if(s2>0)s2=A[i]-x;else s2+=A[i]-x;res=max(res,max(fabs(s1),fabs(s2)));}return res;
}
int main(){while(scanf("%d",&N)!=EOF){for(int i=0;i<N;i++) scanf("%d",&A[i]);double l=-10000,r=10000,m1,m2,a1,a2,ans=1e233;for(int i=0;i<128;i++){m1=l+(r-l)/3;m2=l+(r-l)/3*2;a1=f(m1),a2=f(m2);ans=min(ans,min(a1,a2));if(a1<a2)r=m2;else l=m1;}printf("%.15lf",ans);}return 0;
}