题解 CF578C 【Weakness and Poorness】
swiftc
2019-06-26 18:56:42
#### 我感觉这道题还是三分做比较好吧
首先看到题面，设check(x)为a1-x,a2-x,...,an-x的不美好程度
显然它不是单调的，所以我们用三分来解
三分大家都会吧，那么我们来考虑check(x)怎么求
### 1.暴力求法
直接求出前缀和，然后暴力模拟
代码：
```cpp
//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]不可能使答案变的更大
代码：
```cpp
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)这种我没调出来~~
```cpp
#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;
}
```