CF578C：Weakness and Poorness——题解

题解"/>

CF578C：Weakness and Poorness——题解

——————————————————————————

题目大意：序列的数-x，求最大连续子序列和的绝对值的最小值。

————————————————————————————

没有绝对值的话，明显是单调增的。

将数全部翻转，明显是单调减的。

所以显然是单峰函数，可以三分x做。

要注意精度，循环200就差不多了，不要循环太多次不然会TLE。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int M=200001;
double a[M];
int n;
double suan(double m){double ans=0,sum=0;for(int i=1;i<=n;i++){sum+=a[i]-m;if(sum<0)sum=0;ans=max(ans,sum);}sum=0;for(int i=1;i<=n;i++){sum+=m-a[i];if(sum<0)sum=0;ans=max(ans,sum);}return ans;
}
double sanfen(double l,double r){for(int i=1;i<=200;i++){double midl=(r-l)/3+l;double midr=r-(r-l)/3;if(suan(midl)<suan(midr))r=midr;else l=midl;}return l;
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lf",&a[i]);printf("%.15lf\n",suan(sanfen(-10000,10000)));return 0;
}

转载于:.html