2017-08-27 17:24:07

writer:pprp

题意简述：

• Codeforces 578C Weakness and poorness

• 给定一个序列A

• 一个区间的poorness定义为这个区间内和的绝对值

• weakness等于所有区间最大的poorness

• 求一个x使得，序列A全部减x后weakness最小

• 1 ≤ n ≤ 2 * 1e5

 

这里用到了最大连续区间的和的知识点·，可以看上一篇博客

通过三分找最小值

AC代码如下：

/*@theme:myprogramme codeforces 578c@writer:pprp@declare:三分的思想@date:2017/8/27*/#include 
     
      using namespace std;int n;const int maxn = 2e6+100;double a[maxn], b[maxn];const double eps = 3e-12;//找到连续区间大和double maxSum(double a[]){    double ans = 0, tmp = 0;    for(int i = 0; i < n ; i++)    {        tmp = max(0.0,tmp) + a[i];        ans = max(ans, tmp);    }    return ans;}//对三分的结果进行判断double calc(double x){    for(int i= 0 ; i < n ; i++)    {        b[i] = a[i] - x;    }    double as1 = maxSum(b);    for(int i= 0 ; i < n ; i++)    {        b[i] *= -1;    }    double as2 = maxSum(b);    return max(as1, as2);}//三分查找double  Search(){    double l = -1e4, r = 1e4;    double m, mm;    while(r - l > eps)    {        m = (l*2 + r)/3.0;        mm = (r*2 + l)/3.0;        double as1 = calc(m);        double as2 = calc(mm);        if(as1 < as2)            r = mm;        else            l = m;    }    //找到r对应的区间和最大    return calc(r);}int main(){    scanf("%d", &n);    for(int i = 0 ; i < n ; i++)        cin >> a[i];    printf("%.15f\n",Search());    return 0;}