P1883 函数题解

SunsetSamsara · 2021-04-23 15:41:13 · 题解

我的思路是数学方法，可以通过二次函数的性质来解答。

先看数据范围，发现这些二次函数的首项系数 a \geq 0。

而系数 a \geq 0 的二次函数是开口朝上的抛物线，即这样:

所以，存在数 x=-\dfrac b {2a} （对称轴 x 坐标）使得二次函数 f_k(x) 在区间 (-\infty,x) 上单减，在区间 (x,\infty) 上单增。

于是，函数 f_k(k\in[1,n])都是单峰函数。

那么我们取 \max 之后的 F 也是单峰函数，不严谨证明如下:

若存在两个 x 记作 x_1,x_2 使得 x_1,x_2 都是局部极小值，

那么 (x_1,F(x_1)) 这个点所在的二次函数 f_a 在对方点上的值 f_a(x_2) 要大于 f_a(x_1)，

所以 F(x_1) > f_a(x_1) , 即 (x_1,F(x_1)) 不在的二次函数 f_a 上，矛盾！

即不存在两个 x 使得它们都是 F(x) 的局部极小值。

所以，F(x)是单峰函数。

综上，可以使用三分法解决。

代码如下：

#include<stdio.h>
int A[10001],B[10001],C[10001];
int n;
double calcF(double d){
    double ret=0,t;
    for(int i=1;i<=n;++i){
        t=(A[i]*d+B[i])*d+C[i];
        if(ret<t)ret=t;
    }
    return ret;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
            scanf("%d%d%d",A+i,B+i,C+i);
        double l=0,r=1000,dis=(r-l)/3,lmid=l+dis,rmid=r-dis; //左端点，右端点，用三分点lmid与rmid分界
        while(r-l>1e-9){
        //把大的值赋值给l或r
            if(calcF(lmid)>calcF(rmid))l=lmid;
            else r=rmid;
            dis=(r-l)/3;lmid=l+dis;rmid=(r-dis);
        //再算一遍
        }
        printf("%.4lf\n",calcF(l));
    }
}

P1883 函数 题解

P1883 函数题解