形式化题目

给定 $n$ 个二次函数 $S_i(x) = a_i x^2 + b_i x + c_i$（其中 $a_i \ge 0$），定义复合上包络函数：

求函数 $F(x)$ 在闭区间 $[0, 1000]$ 上的最小值 $\min_{x \in [0, 1000]} F(x)$，结果四舍五入保留 4 位小数。

正解

思路

1. 朴素想法的缺陷

若尝试对每条二次曲线单独求顶点 $-\frac{b_i}{2a_i}$ 的最小值，并取它们中的最小值，这是错误的。因为 $F(x)$ 是所有曲线的点态最大值（上包络），当某一条抛物线处于其自身顶点时，其他抛物线的值可能很大，上包络在该点的值远非全局最小。样例 2 中两条曲线各自顶点处的 $F$ 值均为 $2$，但实际最小值出现在两线交点 $x = 0.5$ 处，值为 $0.5$。

若尝试在 $[0, 1000]$ 内以极小步长离散化暴力枚举，为了保证 4 位小数精度至少需要 $10^7 \sim 10^8$ 次计算，在 $n \le 10000$ 下必定超时。

2. 函数的凸性证明

观察每个单项函数 $S_i(x) = a_i x^2 + b_i x + c_i$：

• 由于题目给定 $a_i \ge 0$，抛物线全部开口向上（当 $a_i = 0$ 时退化为直线）；
• 因此，每个 $S_i(x)$ 在 $\mathbb{R}$ 上都是（下）凸函数。

考虑凸函数的点态最大值函数 $F(x) = \max_{1 \le i \le n} S_i(x)$。根据凸函数定义，对任意 $x_1, x_2 \in [0, 1000]$ 及 $\lambda \in [0, 1]$，对每个 $i$ 均有：

对不等式最左端关于 $i$ 取最大值，可得：

这证明了若干凸函数的最大值复合函数 $F(x)$ 仍然是下凸函数。下凸函数在闭区间 $[0, 1000]$ 上为单峰（单谷）或单调函数，不存在多个局部极小值。

3. 三分法求解

针对下凸函数在闭区间上求最小值的问题，可以使用三分查找（Ternary Search）：

在当前区间 $[lo, hi]$ 内取两个三等分点：

分别计算 $F(m_1)$ 与 $F(m_2)$：

• 若 $F(m_1) < F(m_2)$：极小值点不可能在 $(m_2, hi]$ 范围内（若在 $m_2$ 右侧，则根据下凸性在 $[lo, m_2]$ 上函数必须递减，会有 $F(m_1) \ge F(m_2)$，产生矛盾）。因此可以舍弃右侧三分之一区间，令 $hi \leftarrow m_2$。
• 若 $F(m_1) \ge F(m_2)$：同理，极小值点不可能在 $[lo, m_1)$ 范围内，可以舍弃左侧三分之一区间，令 $lo \leftarrow m_1$。

4. 样例 2 的上包络及收缩示例

以样例 2 为例，$S_1(x) = 2x^2$，$S_2(x) = 2(x-1)^2$：

每轮区间长度均缩短为原来的 $\frac{2}{3}$。迭代 100 次后区间长度为 $1000 \times (\frac{2}{3})^{100} < 10^{-14}$，精度远超题目所需的 4 位小数要求。最终直接返回中点处的 $F$ 值即可。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 10:12
# update_at: 2026-09-30 10:12

import sys


def peak(fs: list[tuple[int, int, int]], x: float) -> float:
    """上包络 F(x) = max(S_i(x)) 在 x 处的函数值。"""
    return max(a * x * x + b * x + c for a, b, c in fs)


def ternary_min(fs: list[tuple[int, int, int]]) -> float:
    """在 [0,1000] 上三分收缩区间，返回凸函数 F 的最小值。

    F 是一堆开口向上抛物线（含退化直线）的逐点最大值，仍是凸函数：
    每次 F(m1) < F(m2) 说明谷底只能在 [lo, m2]，否则只能在 [m1, hi]。
    100 轮后区间长 1000·(2/3)^100，远小于答案精度所需的 5e-11。
    """
    lo, hi = 0.0, 1000.0
    for _ in range(100):
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3
        if peak(fs, m1) < peak(fs, m2):
            hi = m2
        else:
            lo = m1
    return peak(fs, (lo + hi) / 2)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        n = next(data)
        fs = [(next(data), next(data), next(data)) for _ in range(n)]  # n 条曲线 (a,b,c)，元组内从左到右求值
        out.append(f"{ternary_min(fs):.4f}")

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 00:59
 * update_at: 2026-10-05 01:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

typedef long long ll;

ll n;
ll a[MAXN]; // 第 i 条曲线的二次项系数
ll b[MAXN]; // 第 i 条曲线的一次项系数
ll c[MAXN]; // 第 i 条曲线的常数项

// 上包络 F(x) = max_i (a_i * x^2 + b_i * x + c_i)
double envelope(double x) {
    double best = -1e18;
    for (ll i = 0; i < n; i++) {
        double value = a[i] * x * x + b[i] * x + c[i];
        if (value > best) {
            best = value;
        }
    }
    return best;
}

// 每条曲线开口向上（a_i >= 0），凸函数的点态最大值仍是凸函数，
// 所以 F 在 [0,1000] 上单谷，直接三分求最小值。
double ternary_min() {
    double lo = 0.0;
    double hi = 1000.0;
    for (int iter = 0; iter < 100; iter++) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (envelope(m1) < envelope(m2)) {
            hi = m2; // 谷底在左三分之二区间内
        } else {
            lo = m1; // 谷底在右三分之二区间内
        }
    }
    return envelope((lo + hi) / 2);
}

void solve() {
    ll t;
    cin >> t;
    for (ll k = 0; k < t; k++) {
        cin >> n;
        for (ll i = 0; i < n; i++) {
            cin >> a[i] >> b[i] >> c[i];
        }
        printf("%.4f\n", ternary_min());
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

复杂度

• 时间复杂度：计算单点函数值 $F(x)$ 需要遍历 $n$ 条曲线，单次求值复杂度为 $O(n)$。三分查找固定迭代 $K = 100$ 轮，每轮计算 2 次函数值。因此每组测试数据的时间复杂度为 $O(K \cdot n)$。对于 $T \le 10, n \le 10000$，总计算次数在 $2 \times 10^7$ 以内，可以在 1s 左右高效通过。
• 空间复杂度：存储 $n$ 个二次函数的系数元组列表，空间复杂度为 $O(n)$，远低于 128MB 的内存限制。

总结

本题的关键在于利用数学性质识别函数的单谷性：

1. 开口向上的抛物线（$a_i \ge 0$）与直线均为凸函数；
2. 凸函数的点态最大值函数仍保持下凸性；
3. 对单谷下凸函数在连续实数区间求最小值，使用实数三分法可以在对数级轮数内精确逼近极小值点。