swift's blog

swift's blog

题解 CF578C 【Weakness and Poorness】

posted on 2019-06-26 18:56:42 | under 题解 |

我感觉这道题还是三分做比较好吧

首先看到题面,设check(x)为a1-x,a2-x,...,an-x的不美好程度

显然它不是单调的,所以我们用三分来解

三分大家都会吧,那么我们来考虑check(x)怎么求

1.暴力求法

直接求出前缀和,然后暴力模拟

代码:

//fabs为double的abs
double check(double s){
    double ans=-1.0;
    for(int i=1;i<=n;i++){
        a[i]-=s;
    }
    double tmp[200001];
    memset(tmp,0,sizeof(tmp));
    for(int i=1;i<=n;i++){
        tmp[i]=a[i]+tmp[i-1];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            ans=max(ans,fabs(tmp[i]-tmp[j-1]));
        }
    }
    for(int i=1;i<=n;i++){
        a[i]+=s;
    }
    return ans;
}

可以过7个点

2.正解

让我们先求出一个前缀和数组tmp

让我们想一想,可不可以不用对于每一个i都从1~i-1枚举j呢?

因为我们要求最大的fabs(tmp[i]-tmp[j]),所以我们只需要tmp[1]~tmp[i-1]中的最大值和最小值

对于剩下的tmp[j]不可能使答案变的更大

代码:

inline double check(double x){
    double sum=0,ret=0,Min=0,Max=0;
    for(int i=1;i<=n;i++)
    {
        sum+=a[i]-x;
        //因为我们只需要当前的前缀和,所以我们只保留当前的前缀和即可,不需要求tmp数组
        ret=max(ret,fabs(sum-Min));
        ret=max(ret,fabs(sum-Max));
        //更新数列的不美好程度
        Min=min(Min,sum);
        Max=max(Max,sum);
        //更新前缀和的最大值和最小值
    }
    return ret;
}

完整代码:

注意:一定要注意精度

while(r-l>=xxx)这种我没调出来

#ifdef DEBUG
#include"stdc++.h"
#else
#include<bits/stdc++.h>
#endif
using namespace std;
int n;
double a[200001];
inline double check(double x){
    double sum=0,ret=0,Min=0,Max=0;
    for(int i=1;i<=n;i++)
    {
        sum+=a[i]-x;
        ret=max(ret,fabs(sum-Min));
        ret=max(ret,fabs(sum-Max));
        Min=min(Min,sum);
        Max=max(Max,sum);
    }
    return ret;
}
int main(){
    scanf("%d",&n);
    double l=0,r;
    for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
    for(int i=1;i<=n;i++){
        l=min(l,-fabs(a[i]));
    }
    r=-l;
    int cnt=0;
    while(cnt++<400){
        double m1=l+(r-l)/3,m2=r-(r-l)/3;
        double a1=check(m1),a2=check(m2);
        if(a1<a2){
            r=m2;
        }
        else{
            l=m1;
        }
    }
    printf("%.6lf\n",check((l+r)/2.0));
    return 0;
}