P1883 题解

· · 题解

题目传送门

样例解释

对于第 2 个样例，其 2 个函数的图象如图所示。发现当 x=0.5 时，2 个函数的最大值最小，为 0.5。

算法介绍

三分是由二分延伸出的一种算法。但与二分不同的是，二分可以解决答案具有单调性的问题，而三分可以解决单峰或者单谷问题。例如本题所给的二次函数，就是一个单谷函数。

函数需要用浮点类型结构实现，而常用的 double 等类型会误差。所以规定所允许的误差 \varepsilon，本题需保留 4 位小数，故规定 \varepsilon=10^{-9}。

然后进行三分，规定下界 L 和上界 R，循环条件即为 R-L>\varepsilon。所谓三分，就是将其三等分，记两个中间点 M_1 和 M_2，则 M_1=L+\frac{R-L}{3}，M_2=R-\frac{R-L}{3}。计算 F(M_1) 的值与 F(M_2) 的值进行比较。若 F(M_1)<F(M_2)，更新 R\gets M_2；否则更新 L\gets M_1。

正确性证明

更新 R\gets M_2，实则就是去掉区间 (M_2,R]，因为当前 F(M_1) 的值更小，则 M_1 更接近最小值。L\gets M_1 同理。又因为二次函数一定是轴对称的，所以不存在更新区间时直接越过答案。

计算一次 F(x) 的复杂度为 N 级别，三分部分为 \log V 级别。其中，V 是二次函数的值域。整体时间复杂度 \mathcal{O}(T\times N\log V)。

代码实现

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e4+10;
const double EPS=1e-9;
int n,a[N],b[N],c[N];
double calc(double x,int p){ //计算二次函数 f(x)
    return a[p]*x*x+b[p]*x+c[p];
}
double f(double x){ //求最大值 F(x)
    double res=-1e18;
    for(int i=1;i<=n;++i)
        res=max(res,calc(x,i));
    return res;
}
void solve(){
    n=read();
    for(int i=1;i<=n;++i)
        a[i]=read(),b[i]=read(),c[i]=read();
    double l=0,r=1000; //已知 F(x) 在区间 [0,1000] 内
    while(r-l>EPS){
        double lmid=l+(r-l)/3,rmid=r-(r-l)/3.0; //两个中间点
        if(f(lmid)<f(rmid)) //M1 更贴近答案
            r=rmid; //舍去区间 (M2,R]
        else l=lmid; //舍去区间 [L,M1)
    }
    printf("%.4lf\n",f(l)); //最终输出的是 F(x) 的最小值
    return;
}
int main(){
    int T=read();
    while(T--)
        solve();
    return 0;
}

可以做做 P3382 练练手。