题解 | 三分 / 函数 / [ICPC-Chengdu 2010] Error Curves

题干分析

题目要求我们针对一组二次函数(可能退化为一次函数),在区间[0,1000]上取得F(x)的最小值,其中:

算法思路

首先我们简单感受一下F(x)是单峰函数: 具体的证明有些许繁琐,感兴趣的可以自行查资料了解一下. 现在我们只需要找到在区间[0,1000]下这个单峰函数的最小值.我们因此能够采取三分法进行求解.

精度问题

由于是实数三分,且要求保留小数点后四位,三分精度把控不好是很容易出问题的,这里简单解释一下如何确定精度:

• 保留小数点后四位,因此x精度至少应为1e-4.
• a的取值最高为100,范围取值最高为1000,二次项的偏移为axΔx精度至少达到1e-4,所以x精度至少为1e-9.
• b最高取值为5000,一次项偏移为bΔx,须达到1e-4精度,因此x精度至少为1e-8.
• 综合起来并留些余量,三分精度定为1e-10最好.

实现代码

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

class P1883 {
    double F(int n, vector<vector<int>> &params, double x) {
        double res = -DBL_MAX;
        for (int i = 0; i < n; i++) {
            double a = params[i][0], b = params[i][1], c = params[i][2];
            res = max(res, a * x * x + b * x + c);
        }
        return res;
    }

public:
    double solve(int n, vector<vector<int>> &params) {
        double left = 0, right = 1000;
        while (right - left > 1e-10) {
            double delta = (right - left) / 3;
            double mid1 = left + delta, mid2 = right - delta;
            double f1 = F(n, params, mid1), f2 = F(n, params, mid2);
            if (f1 <= f2) right = mid2;
            else left = mid1;
        }
        return F(n, params, left);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    P1883 p;
    for (int _ = 1; _ <= T; _++) {
        int n;
        cin >> n;
        vector params(n, vector<int>(3));
        for (int i = 0; i < n; i++) {
            cin >> params[i][0] >> params[i][1] >> params[i][2];
        }
        printf("%.4lf\n", p.solve(n, params));
    }
    return 0;
}

复杂度分析

• 时间复杂度: 三分次数共计log(m/b)次,其中m为区间长度,b为精度,每次计算耗时O(n),总时间复杂度为O(nlog(m/b));
• 空间复杂度: 全过程只消耗常数的额外空间,因此空间复杂度为O(1).