[codeforces] 578C Weakness and Poorness

codeforces] 578C Weakness and Poorness"/>

[codeforces] 578C Weakness and Poorness

原题

题目定义了两个变量：
poorness表示一个区间内和的绝对值。
weakness表示一个所有区间最大的poornesss
题目要求你求一个x使得
a1 − x, a2 − x, ..., an − x这个序列的weakness最小
输出最小的weakness

显然，所求值是这样的一个函数

（因为是对abs取max，所以不可能出现有两个谷的不符合要求的函数）
所以我们可以三分，只有当x为ans时，我们才会得到最小值。
已知x时，如何求解最大子段和呢？，因为我们是取abs，所以在记录b[i]为前缀和时，b[i]为结尾的最大子段和要么由前面最小的b[]得到，要么由前面最大的b[]得到。所以我们只要O(n)前缀和然后枚举判断找答案就可以了。

#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 2000010
#define eps 3e-12
using namespace std;
int n,a[N];
double l,r,b[N];int read()
{int ans=0,fu=1;char j=getchar();for (;(j<'0' || j>'9') && j!='-';j=getchar()) ;if (j=='-') fu=-1,j=getchar();for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';return ans*fu;
}double check(double x)
{double mn=100000,mx=-100000,ans=0;for (int i=1;i<=n;i++) b[i]=(double)a[i]-x;for (int i=1;i<=n;i++) b[i]+=b[i-1];ans=fabs(b[1]),mn=min(0.0,b[1]),mx=max(0.0,b[1]);for (int i=2;i<=n;i++) {ans=max(ans,fabs(b[i]-mn));ans=max(ans,fabs(b[i]-mx));mn=min(mn,b[i]),mx=max(mx,b[i]);}return ans;
}int main()
{while (~scanf("%d",&n)){for (int i=1;i<=n;i++)a[i]=read();l=-100000;r=100000;while (r-l>eps){double midl=l+(r-l)/3;double midr=r-(r-l)/3;if (check(midl)<check(midr)) r=midr;else l=midl;}printf("%.9lf\n",check(l));}return 0;
}

转载于:.html