曲线

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1202 字

三分法求多个二次函数最大值的最小值

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1435
// 题意：给定 n 个二次函数 S_i(x) = ax^2 + bx + c，令 F(x) = max(S_i(x))，求 F(x) 在 [0, 1000] 上的最小值，保留四位小数。
// 思路：三分法。
// 1. 开口向上的二次函数的最大值函数 F(x) 仍是单峰（下凸）函数，可以用三分求极值。
// 2. 每次取三等分点 m1、m2，若 F(m1) < F(m2) 则极值在左侧，否则在右侧。
// 复杂度：O(T * n * log(1/eps)) 时间 / O(n) 空间
// 易错点：二次函数可能退化成一次函数（a = 0），但取最大值后依然是下凸的，三分照样成立。
// 易错点：三分要迭代足够多次（80 次以上），否则四位小数的精度达不到，输出要用 fixed << setprecision(4)。
#include <bits/stdc++.h>
using namespace std;
struct Fun {
    double a, b, c;
};
int main(){
    int T;
    if(!(cin >> T)) return 0;
    while(T--){
        int n;
        cin >> n;
        vector<Fun> f(n);
        for(int i = 0; i < n; i++) cin >> f[i].a >> f[i].b >> f[i].c;
        auto calc = [&](double x){
            double res = -1e100;
            for(int i = 0; i < n; i++) res = max(res, f[i].a * x * x + f[i].b * x + f[i].c);
            return res;
        };
        double l = 0, r = 1000;
        for(int it = 0; it < 100; it++){
            double m1 = l + (r - l) / 3;
            double m2 = r - (r - l) / 3;
            if(calc(m1) < calc(m2)) r = m2;
            else l = m1;
        }
        cout << fixed << setprecision(4) << calc((l + r) / 2) << "\n";
    }
    return 0;
}

曲线

正文

一本通·提高篇的其它内容