1 条题解

  • 0
    @ 2024-12-20 23:23:16

    观察题目图像得 F(x)F(x) 函数是一个下凸函数。即对于任意的 x1<x2<x3x1<x2<x3 ,不存在 F(x1)<F(x2)>F(x3)F(x1)<F(x2)>F(x3) ,根据这个定义,我们可以通过三分法求该函数的最值。注:本人的三分法是自己推算来的,效率可能不高,请大家谅解!

    随便画出二次函数的一段(二次函数是一个特殊的下凸函数),我们发现一个下凸函数其上四个点无非有以下几种情况:

    设下凸函数上四个点横坐标分别为 x1<x2<x3<x4x1<x2<x3<x4 ,并且我们已经确定该函数的最小值在 [x1,x4][x1,x4] 之间

    F(x1)<F(x2)F(x1)<F(x2) ,则函数的最小值的 xx 的取值范围一定在 [x1,x2][x1,x2] 之间,因为根据定义,若有 F(x1)<F(x2)F(x1)<F(x2) ,必有 F(x1)<F(x2)<F(x3)<F(x4)F(x1)<F(x2)<F(x3)<F(x4)

    F(x3)>F(x4)F(x3)>F(x4) ,同理可得,函数最小值的取值范围一定是在 [x3,x4][x3,x4] 之间。

    F(x1)>F(x2)F(x1)>F(x2) && F(x2)<F(x3)F(x2)<F(x3) ,则函数的最小值的x的取值范围一定在 [x1,x3][x1,x3] 之间,因为下凸函数有且仅有一个低谷,并且下凸函数的最小值在低谷中。

    F(x4)>F(x3)F(x4)>F(x3) && F(x3)<F(x2)F(x3)<F(x2) ,同理,函数最小值的取值范围一定在 [x2,x4][x2,x4] 之间。

    最后就只剩下一种情况了,此时函数最小值的取值范围一定在 [x2,x3][x2,x3] 之间。

    由此,我们可以设计出代码(请认真阅读注释):

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=10010;
    const double inf=2e9;
    int T,n;
    double a[maxn],b[maxn],c[maxn],l,r,mid1,mid2,ret,v1,v2,v3,v4;
    inline double f(double x){ret=-inf;for(int i=0;i<n;i++)ret=max(ret,a[i]*x*x+b[i]*x+c[i]);return ret;}//内置的计算F(x)函数的值的函数
    int main()
    {
        scanf("%d",&T);//多组数据
        while(T--)
        {
            scanf("%d",&n);
            for(int i=0;i<n;i++)scanf("%lf%lf%lf",a+i,b+i,c+i);//读入
            l=0;r=1000;//左范围和右范围如题目中所示
            while(l+1e-10<r)//这里是为了减小b*x所带来的误差增大化,亦可以写成f(l)+1e-5<f(r)
            {
                mid1=(l+l+r)/3;mid2=(l+r+r)/3;//用区间[l,r]的三分点作为分界,每次至少都能使答案范围减小1/3
                v1=f(l);v2=f(mid1);v3=f(mid2);v4=f(r);//提前计算出值,避免做重复计算
                if(v1<v2)r=mid1;
                else if(v4<v3)l=mid2;
                else if(v1>v2&&v2<v3)r=mid2;
                else if(v4>v3&&v3<v2)l=mid1;
                else l=mid1,r=mid2;//根据上面分析中得出的公式可得,安排成这样的顺序是为了一次削减尽量多的无用部分,从而加快速度
            }
            printf("%.4lf\n",f(l));
        }
        return 0;
    }
    

    时间复杂度大约是 O(Tnlg(1013))O(T*n*lg(10^{13})) ,在题目所允许的时间范围内。本人亲测 584msAC584ms AC,速度比较快。

    • 1

    信息

    ID
    166
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    11
    已通过
    8
    上传者