p1883

问题分析

给定 个二次函数（可能退化为一次函数），定义 。要求 在区间 上的最小值，结果精确到小数点后四位。

是多个二次函数的最大值函数，其图像为上包络线（upper envelope）。该函数在区间 上连续，但可能不是凸函数（因为二次项系数 可能为负）。 的最小值可能出现在：

• 区间端点 或
• 某个二次函数的顶点（如果在 内且在该点处取最大值）
• 两个二次函数的交点（分段点）

由于 可能较大（如 ），枚举所有交点（）不可行。但观察到 在 上通常呈现单峰性（先减后增），可以使用三分搜索（ternary search）高效逼近最小值点。

三分搜索原理

三分搜索适用于单峰函数。在区间 内取两点 和 ：

• 若 ，则最小值在 内，令
• 若 ，则最小值在 内，令

迭代足够次数（如 100 次）后，区间 足够小，再在区间内取若干点计算 取最小值。

算法步骤

1. 初始化：计算端点 和 处的 值，作为初始答案。
2. 三分搜索：迭代 100 次：
   • 计算 和 处的 和
   • 更新答案（取当前最小值）
   • 根据 和 的大小关系缩小区间
3. 精细搜索：在最终区间 内取 11 个等分点，计算 并更新答案。
4. 输出：将答案四舍五入到小数点后四位。

复杂度分析

• 每次计算 需 时间。
• 三分搜索 100 次，每次计算两个点，共 。
• 精细搜索 11 个点，共 。
• 加上两个端点，总计算点数 。
• 对于 和 组数据，总操作数约 ，在 C++ 中可接受。

代码实现

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

struct Func {
    int a, b, c;
    Func(int a = 0, int b = 0, int c = 0) : a(a), b(b), c(c) {}
};

double F(double x, vector<Func>& funcs) {
    double res = -1e300; // 负无穷大
    for (const Func& f : funcs) {
        double value = static_cast<double>(f.a) * x * x + 
                       static_cast<double>(f.b) * x + 
                       static_cast<double>(f.c);
        if (value > res) res = value;
    }
    return res;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        vector<Func> funcs;
        for (int i = 0; i < n; i++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            funcs.push_back(Func(a, b, c));
        }

        double ans = 1e300; // 正无穷大
        ans = min(ans, F(0.0, funcs));
        ans = min(ans, F(1000.0, funcs));

        double l = 0.0, r = 1000.0;
        for (int iter = 0; iter < 100; iter++) {
            double m1 = l + (r - l) / 3.0;
            double m2 = r - (r - l) / 3.0;
            double f1 = F(m1, funcs);
            double f2 = F(m2, funcs);
            ans = min(ans, f1);
            ans = min(ans, f2);
            if (f1 < f2) {
                r = m2;
            } else {
                l = m1;
            }
        }

        for (int i = 0; i <= 10; i++) {
            double x = l + (r - l) * i / 10.0;
            ans = min(ans, F(x, funcs));
        }

        printf("%.4f\n", ans);
    }
    return 0;
}

关键点说明

1. 精度处理：使用 double 类型存储中间结果，避免整数溢出和浮点误差。
2. 初始值设置：ans 初始化为极大值 1e300，F(x) 计算时 res 初始化为极小值 -1e300。
3. 三分搜索迭代次数：100 次确保区间长度 ，远小于 。