UKE

kkksc03 怎么UKE了？ #include #include #include #include using namespace std; const double eps=1e-8; const int maxn=2e5+5; int arr[maxn]; double arr1[maxn]; int n; double calc(double arr[]){ double t=0; double res=arr[0]; for (int i=0;i<n;++i){ t=arr[i]+t; res=max(res,t); if (t<0+eps){ t=0; } } return res; } double solve(double t){ for(int i=0;i<n;++i) arr1[i]=arr[i]-t; double x1=calc(arr1); for (int i=0;i<n;++i) arr1[i]=-arr1[i]; double x2=calc(arr1); double x=max(fabs(x1),fabs(x2)); return x; } int main(){ scanf("%d",&n); int maximum=-10001,minimum=10001; for(int i=0;i<n;++i){ scanf("%d",arr+i); maximum=max(arr[i],maximum); minimum=min(arr[i], minimum); } int dcnt=100; double l=minimum,r=maximum; while(dcnt--){ double m1=l+(r-l)/3,m2=l+(r-l)*2/3; double x1=solve(m1),x2=solve(m2); if(x1>x2){ l=m1; } else r=m2; } double res=solve(l); printf("%.6f\n",res); return 0; }