codeforces578C. Weakness and Poorness

本文主要是介绍codeforces578C. Weakness and Poorness，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：http://codeforces.com/problemset/problem/578/c

思路：设f(x)为取x时的最大子段和，f(x)是先减后增的，于是可以用三分法求最值

先确定初始区间[l,r]，mid1=(l+r)/2,mid2=(mid1+r)/2

O(n)求出f(mid1)和f(mid2)

若f(mid1)>f(mid2)则令l=mid1

否则令r=mid2

直到精度达到结束

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long double ld;
const ld eps=1e-12;
const int maxn=200010;
using namespace std;
double a[maxn];ld b[maxn];int n;ld getans(){ld res=0.0,ans=-1.0;for (int i=1;i<=n;i++){res+=b[i];if (res<0) res=0;ans=max(ans,res);}return ans;
}ld f(ld x){ld ans=-1.0;for (int i=1;i<=n;i++) b[i]=a[i]-x;ans=getans();for (int i=1;i<=n;i++) b[i]*=-1.0;ans=max(ans,getans());return ans;
}int main(){scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%lf",&a[i]);ld l=-10000.0,r=10000.0,mid1,mid2,res1=-1,res2=-1;while (l+eps<=r){mid1=(l+r)/2,mid2=(mid1+r)/2;res1=f(mid1),res2=f(mid2);if (res1>res2+eps) l=mid1;else if (res2>res1+eps) r=mid2;else break;}printf("%.15lf\n",(double)res1);return 0;
}

这篇关于codeforces578C. Weakness and Poorness的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---