洛谷P1883-函数-题解

函数

题目描述

给定 $n$ 个二次函数 $f_1(x),f_2(x),\dots,f_n(x)$（均形如 $ax^2+bx+c$），设 $F(x)=\max\{f_1(x),f_2(x),...,f_n(x)\}$，求 $F(x)$ 在区间 $[0,1000]$ 上的最小值。

输入格式

输入第一行为正整数 $T$，表示有 $T$ 组数据。

每组数据第一行一个正整数 $n$，接着 $n$ 行，每行 $3$ 个整数 $a,b,c$，用来表示每个二次函数的 $3$ 个系数，注意二次函数有可能退化成一次。

输出格式

每组数据输出一行，表示 $F(x)$ 的在区间 $[0,1000]$ 上的最小值。答案精确到小数点后四位，四舍五入。

样例 #1

样例输入 #1

2
1
2 0 0
2
2 0 0
2 -4 2

样例输出 #1

0.0000
0.5000

提示

对于 $50\%$ 的数据，$n\le 100$。

对于 $100\%$ 的数据，$T<10$，$\ n\le 10^4$，$0\le a\le 100$，$|b| \le 5\times 10^3$，$|c| \le 5\times 10^3$。

P1883 函数 - 洛谷

思路

由题目可以知道，这是一到对$F(x)=\max\{f_1(x),f_2(x),...,f_n(x)\}$在 $[0,1000]$ 上求最值的问题。而 $f_1(x),f_2(x),\dots,f_n(x)$ 均为二次函数，故 $F(x)$ 满足单调性，且范围已给出，满足浮点数二分和三分的条件。

根据我们P3382-【模板】三分法的题解可得，对$F(x)$ 求最值可以用求导二分或者直接三分的方法，这里为了方便直接使用三分法。

• 三分答案

C++代码

#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
template<typename T>
T binary_search_answer(T l, T r,
                       function<bool(const T&, const T&)> isKeep,
                       function<bool(const T&)> check) {
    while (isKeep(l, r)) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(); cout.tie();
    int t, n, o;
    int a[10][10000], b[10][10000], c[10][10000];
    auto f = [&](double x, int i) {
        return a[o][i] * x * x + b[o][i] * x + c[o][i];
    };
    auto F = [&](double x) {
        double res = 0;
        for (int i = 0; i < n; i++)
            res = std::max(res, f(x,i));
        return res;
    };
    cin >> t;
    for (int i = 0; i < t; ++i) {
        cin >> n;
        o = i;
        for (int j = 0; j < n; ++j)
            cin >> a[i][j] >> b[i][j] >> c[i][j];
        cout << fixed << setprecision(4)
        << F(binary_search_answer<double>(0, 1000,
             [](const double &l, const double &r)
                { return abs(r - l) > 1e-8; },
             [&](const double &x)
                { return F(x + 1e-8) < F(x - 1e-8); }
             )) << endl;
    }
    return 0;
}

AC截图

C with STL代码

#include <algorithm>
#include <cstdio>
#include <cmath>

int t, n, o;
int a[10][10000], b[10][10000], c[10][10000];
double f(double x, int i) {
    return a[o][i] * x * x + b[o][i] * x + c[o][i];
}
double F(double x) {
    double res = 0;
    for (int i = 0; i < n; i++)
        res = std::max(res, f(x,i));
    return res;
}
double binary_search_answer() {
    double l = 0, r = 1000;
    while (fabs(r - l) > 1e-8) {
        double mid = (l + r) / 2;
        if (F(mid + 1e-8) < F(mid - 1e-8)) l = mid;
        else r = mid;
    }
    return l;
}

int main() {
    scanf("%d", &t);
    for (int i = 0; i < t; ++i) {
        scanf("%d", &n);
        o = i;
        for (int j = 0; j < n; ++j)
            scanf("%d%d%d", &a[i][j], &b[i][j], &c[i][j]);
        printf("%.4lf\n", F(binary_search_answer()));
    }
    return 0;
}

AC截图