【題解】Codeforces 578C. Weakness and Poorness

【題目敘述】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);
    }
}
分享本文 Share with friends