CodeForces 578C (Weakness and Poorness)[三分]

发表于 | 更新于 | | 阅读次数：

题目链接：http://codeforces.com/problemset/problem/578/C

可以看出weakness-x是一个单峰函数，可以使用三分。
然后就是求区间最大子段和。简化问题这里假设只求正最大子段和，dp[i-1]转移到b[i]时，不论b[i]是正是负，若dp[i-1]是正则一定会对它产生“正面影响”，此时dp[i]=dp[i-1]+b[i]；若dp[i-1]是负则一定会对b[i]产生“负面影响”，此时应该扔掉dp[i-1]，dp[i]=b[i]。
题目要求求出正负最大子段和，这里只需要对b[i]求一遍正最大子段和，再把b[i]取反，再求一遍最大子段和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
const double EPS=1e-6;
const int maxn=200010;
int n;
int a[maxn];
double b[maxn];
double dp[maxn];
double f(double mid) {
	double ans=0;
	for(int i=1;i<=n;i++) {
		b[i]=a[i]-mid;
	}
	dp[0]=0;
	for(int i=1;i<=n;i++) {
		if(dp[i-1]>0) dp[i]=dp[i-1]+b[i];
		else dp[i]=b[i];
		ans=max(ans,fabs(dp[i]));
	}
	for(int i=1;i<=n;i++) {
		b[i]=mid-a[i];
	}
	dp[0]=0;
	for(int i=1;i<=n;i++) {
		if(dp[i-1]>0) dp[i]=dp[i-1]+b[i];
		else dp[i]=b[i];
		ans=max(ans,fabs(dp[i]));
	}
	return ans;
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",a+i);
	}
	double l=-10001,r=10001;
	double m,mm,ma,mma;
	int t=100;
	while(t--) {//(fabs(r-l)>=1e-10) {
		m=(2*l+r)/3;
		mm=(l+2*r)/3;
		ma=f(m);
		mma=f(mm);
		if(ma<mma) r=mm;
		else l=m;
	}
	printf("%.15lf",f(l));
}