题解 P1883 【函数】

· · 题解

三分做法

题意很清楚，不复述了。

前置知识:三分

这道题要求最值，那么就想到了二分答案。但是又发现枚举的答案是一个浮点数，所以我们就可以用三分来做，check部分也已经很明显了（就是题目···）。

大概讲讲三分。

三分的原理与二分的原理相同,但不同的是，三分对于已知的l与r，会计算两个三等分点的值，当l与r的差可以忽略不计（与浮点数误差差不多）时，就以任意端点输出即可。

代码（libreOJ修改后码风）

#include <stdio.h>
#include <algorithm>//我不喜欢万能头。
using namespace std;
const double eps = 1e-9;//注意精度，1-e5在我学校的OJ是0分 。
int T;
int n;
int a[10005], b[10005], c[10005];
double l, r, m1, m2;
double get(double x) {
    double Max = 0;

    for (int i = 1; i <= n; i++)
        Max = max(Max, a[i] * x * x + b[i] * x + c[i]);

    return Max;
    //根据题意模拟即可。
}
int main() {
    scanf("%d", &T);

    while (T--) {
        scanf("%d", &n);

        //printf("%d\n",n);
        for (int i = 1; i <= n; i++)
            scanf("%d %d %d", &a[i], &b[i], &c[i]);

        l = 0.0, r = 1000.0;//F(x)在[0,1000]区间

        while (r - l > eps) {
            m1 = (l * 2 + r) / 3;//三等分点
            m2 = (l + r * 2) / 3;

            if (get(m1) > get(m2))
                l = m1;
            else
                r = m2;
        }//三分板子···

        printf("%.4lf\n", get(l));
    }

    return 0;
}