洛谷-P1883 【模板】三分 / 函数题解

题目链接：https://www.luogu.com.cn/problem/P1883

题解：求多个二次函数最大值的最小值

题目大意

给定 n 个形如 f_i(x) = a_i x^2 + b_i x + c_i 的二次函数（允许退化为一次函数），定义

F(x) = max{f_1(x), f_2(x), ..., f_n(x)}

求 F(x) 在区间 [0, 1000] 上的最小值。

输出结果保留小数点后四位，四舍五入。

关键观察

每个 f_i(x) 是凸函数或线性函数因为题目保证 a_i >=0（输入范围：0 <= a <= 100$），所以每个 f_i(x) 要么是开口向上的抛物线，要么是一次常数函数 —— 均为凸函数。
F(x) = max{f_i(x)} 是凸函数凸函数的逐点最大值仍是凸函数。因此，F(x) 在 [0,1000]上是单谷函数（先减后增，或单调），存在唯一全局最小值。
可使用三分法求最小值对于单谷函数，可用三分查找在区间内逼近最小值点。

算法设计

目标函数：func(x) 计算 F(x) = max_i f_i(x)。对每个函数，用 Horner 法快速求值：cur = (a*x + b)*x + c。
三分查找：在 [0, 1000] 上不断缩小区间；比较 func(mid1) 与 func(mid2)：若 func(mid1) > func(mid2)，说明最小值在右半部分，令 l = mid1；否则，最小值在左半部分，令 r = mid2。
终止条件：当区间长度小于 eps = 1e-9 时停止，保证精度远高于 10^(-4)。
返回值：最终返回 func(l)（或 func((l+r)/2)），即最小函数值。

注意：本题要求的是 F(x) 的最小值（函数值），而非取得最小值的 x，因此最后调用 func(l)。

代码实现细节

使用 vector<vector<double>> vec 存储每组数据的系数；
func(x) 遍历所有函数，计算其在 x 处的值，取最大值；
主循环处理 T 组测试数据；
输出使用 printf("%.4f\n", ans) 确保四舍五入到小数点后四位。

源代码

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

const double eps = 1e-9;
int t, n;
vector<vector<double>> vec(10001, vector<double>(3));

// 计算 F(x) = max{ f_i(x) }
double func(double x) {
    double res = 0;
    // 计算第一个函数
    double cur = 0;
    for (int j = 0; j < 3; ++j)
        cur = cur * x + vec[0][j];
    res = cur;

    // 计算其余函数并取最大值
    for (int i = 1; i < n; ++i) {
        cur = 0;
        for (int j = 0; j < 3; ++j)
            cur = cur * x + vec[i][j];
        res = max(res, cur);
    }
    return res;
}

// 三分法求 F(x) 在 [0,1000] 上的最小值
double process() {
    double l = 0.0, r = 1000.0;
    while (r - l > eps) {
        double mid1 = l + (r - l) / 3.0;
        double mid2 = r - (r - l) / 3.0;
        if (func(mid1) > func(mid2))
            l = mid1;
        else
            r = mid2;
    }
    return func(l); // 返回最小函数值
}

int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> vec[i][0] >> vec[i][1] >> vec[i][2];
        }
        double ans = process();
        printf("%.4f\n", ans);
    }
    return 0;
}