【題目敘述】https://codeforces.com/contest/578/problem/C
【解題想法】三分搜 (Ternary Search) 【筆記】
- 利用三分搜來逼近答案(近似解)
- 題目要求找出最小的weakness
- weakness：所有區間 (連續子序列) 的poorness值的最大值
- poorness：區間和的絕對值
- func(x)：計算所有值各減 x 後的poorness。利用前綴和求解(下圖)。
- main( )：重複逼近求解
- 設定左界 (l) 和右界 (r)
- 任意選中間兩點 ml 和 mr
#include <iostream>
#include <iomanip>
using namespace std;
int n;
double a[200005];
double mn, mx, l, r, ml, mr;
double cur;
double func(double x){
cur = 0;
mn = 0;
mx = 0;
for (int i = 0; i < n; i++){
cur += a[i] - x;
mn = min(mn, cur);
mx = max(mx, cur);
}
return (mx - mn);
}
int main() {
while (cin >> n){
for (int i = 0; i < n; i++){
cin >> a[i];
}
l = -10000;
r = 10000;
for (int i = 0; i < 100; i++){
ml = (l + r) / 2.0;
mr = (ml + r) / 2.0;
if (func(ml) < func(mr)) r = mr;
else l = ml;
}
cout << fixed << setprecision(10) << func(l);
}
}