Codeforces Round #320 (Div. 1) C. Weakness and Poorness（三分）
最后更新于：2022-04-01 15:52:49
对这个数列中的每一个数减去一个相同的数字， 其最大连续和会呈现出单峰函数的现象， x过大或者过小都不行， 那么处理方法显然是三分。
由于该题不是直接三分的答案， 因此三分出的x虽然精度在答案范围内， 但是求出的最大连续和却不一定满足精度。
二分或三分浮点数时， 最稳妥的方法是根据数据范围自己设置二分或三分的次数， 这样使得精度可以最大化的精确。
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) a>b?a:b
#define Min(a,b) a<b?a:b
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double INF = 100000;
const int maxn = 200000+5;
int T,n,m;
double a[maxn];
double C(double x) {
double ans = 0, cur = 0, cnt1 = 0;
for(int i=0;i<n;i++) {
cur += (a[i]-x);
cnt1++;
if(cur > ans) ans = cur;
if(cur < 0) cur = 0, cnt1 = 0;
}
double ans2 = 0, cur2 = 0, cnt2 = 0;
for(int i=0;i<n;i++) {
cur2 += -(a[i]-x);
if(cur2 > ans) ans = cur2;
if(cur2 < 0) cur2 = 0;
}
return max(ans, ans2);
}
int main() {
while(~scanf("%d",&n)) {
for(int i=0;i<n;i++) {
scanf("%lf",&a[i]);
}
double l = -INF, r = INF, mid, mmid;
T = 100;
while(T--) {
mid = (l+r)/2.0;
mmid = (mid+r)/2.0;
if(C(mid) < C(mmid)) r = mmid;
else l = mid;
}
printf("%.6f\n",C(r));
}
return 0;
}
~~~