题解：P1883 【模板】三分 | 函数

zhaisx · 2025-05-03 08:50:25 · 题解

三分

学过三分的 dalao 可以直接去看思路。

众所周知，二分是在左右边界中折半查找。虽然这道题可以求导数再二分，但对于在上初中的本蒟蒻就不太友好了。QwQ

所以就有另一种十分友好的方法——三分。

所谓三分，本质上是找到两个中间点 u 和 v。一般可以先进行二分，在区间 \left[l, r\right] 中找到中点 m，然后将 u 和 v 分别设为 m 加减一个极小的值 \varepsilon，即

此时，对于一个在 \left[l, r\right] 内的单谷函数 f(x)（只存在一个点 p，在 \left[l, p\right) 上单调递增，在 \left(p, r\right] 上单调递减），如果 f(u) < f(v)，则区间 \left(m, r\right] 可以舍去。（如下图所示）

反之，如果 f(u) > f(v)，则区间 \left[l, m\right) 可以舍去。（如下图所示）

如果 f(u) = f(v) 呢？那答案不就是 m 吗！（如下图所示）

一直重复以上过程，直到 l + \varepsilon \geq r 为止。

思路

观察本题，发现是对函数 F(x) 求最小值，则考虑三分。

首先要确定 F(x) 为单谷函数。证明如下：

如果 F(x) 不是单谷函数，则图像为下图中实线部分。

但显然，虚线部分总是比实现部分大，则 F(x) 只能为虚线部分。虚线部分显然为单谷函数，则 F(x) 为单谷函数。

直接进行三分即可。

代码

#include <bits/stdc++.h>
using namespace std;

int n, a[10005], b[10005], c[10005];

double f(double x) {
    double y = INT_MIN;
    for (int i = 1; i <= n; i++)
        y = max(y, a[i] * x * x + b[i] * x + c[i]);
    return y;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i] >> b[i] >> c[i];
        double l = 0, r = 1000, m, e = 1e-9;
        while (l + e < r) {
            m = (l + r) / 2;
            double u = m - e, v = m + e;
            double fu = f(u), fv = f(v);
            if (fu < fv)
                r = m;
            else if (fu > fv)
                l = m;
            else {
                l = m;
                r = m;
            }
        }
        cout << fixed << setprecision(4) << f((l + r) / 2) << '\n';
    }
    return 0;
}

附言

由于精度问题，\varepsilon 要取 10^{-9}。