题解 P1883 【函数】

· · 题解

这道题主要考了一点关于函数的知识罢，题目大意是给你一堆二次函数，F(x)定义为对于每一个x取每一个函数对应的y的最大值，题目是求F[x]在一定区间中的最小值。

因为同时考虑100个函数有些过于困难，我决定先从简单的两个函数开始

如图

我们可以看到，这里函数的最小值很容易找见，同时我们关注到整个函数是一个下凸函数。

我们知道，开口向上的二次函数是下凸函数，那么假使两个下凸函数取最大值还是下凸函数，就说明题目给的F(x)是一个下凸函数，我们就可以用三分法来寻找最值。

换而言之，本题的难点在于

已知f(x),g(x)为下凸函数，证明h(x)=max(f(x),g(x))是一个下凸函数。

证明如下

对于任意的0\leq\alpha\leq1

总有f(\alpha{x1}+(1-\alpha)x2)\leq\alpha{f(x1)}+(1-\alpha){f(x2)}\leq\alpha{h(x1)}+(1-\alpha){h(x2)}

同理，对于g(x)也有相似的结论

那么很容易推出

h(\alpha{x1}+(1-\alpha)x2)=max(f(\alpha{x1}+(1-\alpha)x2),g(\alpha{x1}+(1-\alpha)x2))\leq\alpha{h(x1)}+(1-\alpha){h(x2)}

这就证明了h(x)是一个凸函数。

那么我们只需要在上面跑个三分求最值就ok了。

更新

2025/4

ans初始化成了-1e9，这样应该就不会被hack了

AC代码

#include<bits/stdc++.h>
#define ri register int
using namespace std;
int T;
int n;
int a[100010],b[100010],c[100010];
double clac(double x)                   //计算某一点的h(x) 
{
    double ans=-1e9;
    for(ri i=1;i<=n;i++)
    ans=max(ans,a[i]*1.0*x*x+b[i]*1.0*x+c[i]);
    return ans;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(ri i=1;i<=n;i++)
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
        double l=0,r=1000;
        while(fabs(r-l)>1e-9)               //三分 
        {
            double mid1=(l+r)/2,mid2=(mid1+r)/2;
            if(clac(mid1)>clac(mid2))   l=mid1;
            else                        r=mid2;
        }
        printf("%.4lf\n",clac(l));
    }
}