P1883 【模板】三分 | 函数

· · 题解

我们知道，二分可以对单调函数求解近似解。它通过一步一步缩小答案的区间范围，最终确定答案。

三分也是一种类似的算法。

对一个定义域为 (l,r) 的函数 f(x) 如果其在 (l,a) 单调递增 ,在 (a,r) 单调递减，那么 f(x) 我们习惯称其为单峰函数，显然 f(a) 是 f(x) 的最大值。

引用百度百科

单峰函数是在所考虑的区间中只有一个严格局部极大值(峰值)的实值函数。如果函数 f(x) 在区间 [a, b] 上只有唯一的最大值点 C ，而在最大值点 C 的左侧，函数单调增加；在点 C 的右侧，函数单调减少，则称这个函数为区间 [a, b] 上的单峰函数。

类似地，我们得到单谷函数的定义。

例如，对于二次项系数大于 0 的二次函数，是单谷函数，二次项系数小于 0 则为单峰函数。

特殊地，我们将一次函数也视为单峰函数和单谷函数。

三分，则可以对于单谷函数或单峰函数，确定它的极大值和极小值。

~其实不用严格单调也可以~

考虑以下代码

double l=0,r=1000;
while(r-l>eps){
    double mid1=(2*l+r)/3;
    double mid2=(l+2*r)/3;
    if(f(mid1)<f(mid2)){
        r=mid2;
    }else{
        l=mid1;
    }
}

对于一个区间 [l,r]，已知 单谷函数f(x) 在其上有最小值。

我们取两个点。

mid_1=l+\frac{r-l}{3}=\frac{2l+r}{3} mid_2=l+\frac{2(r-l)}{3}=\frac{l+2r}{3}

即 mid_1,mid_2 是 [l,r] 的三等分点。

当 f(mid_1)<f(mid_2) ，假设 a \in [mid_2,r]，那么由于 [l,mid_2] 上肯定单调递减，故与 f(mid_1)<f(mid_2) 矛盾。故当 f(mid_1)<f(mid_2) ，a \in [l,mid_2] 。

同理，可以得到 f(mid_1)>f(mid_2) 时，a \in [mid_1,r] （等号可以任取）。

所以，我们就可以通过，f(mid_1) 与 f(mid_2) 的大小关系，一步一步缩小极值点 a 的范围。

对于整数上的二分和三分，我们终止算法的条件写成 l \le r 便可以。但这道题要在实数上进行三分，所以当区间范围被缩小到某一个值时，我们就可以近似将这个区间视为一个点了。即 r-l>eps , eps 就是三分的精度值，eps 越小，便离实际答案越接近。这道题中我们取 eps=10^{-9} 。

关于其时间复杂度，

在三分中，每次可以将目前的范围缩小到 \frac{2}{3}。故 f(x) 的计算次数 k 有 m(\frac{2}{3})^k=eps，k=log_{\frac{2}{3}}\frac{eps}{m}，此题中 eps 为 10^{-9} , m 为 10^3 。

故时间复杂度为 O(t\log \frac{eps}{m}) , 其中 t 为 f(x) 计算一次的复杂度。

在我们掌握了三分法之后，回到这个题目。结合题目的标题我们很显然能直接猜到 F(x) 是一个单谷函数。

具体地，我们怎么去理性地得到这个结论呢？

考虑数学归纳法

已知 f_i(x) 是一个单谷函数（无论它是一次函数还是二次函数）。

假设 \max \{f_1(x),f_2(x),\cdots,f_{i-1}(x)\} 是单谷函数。

则只要证明 max\{\max \{f_1(x),f_2(x),\cdots,f_{i-1}(x)\},f_i(x)\} 是单谷函数。

则要证 若 f(x),g(x) 为单谷函数，则 max\{f(x),g(x)\} 为单谷函数。

关于这一点，通过图像上可以轻易地去理解，但是证明较为困难，三位同学给出的证明包括，

总之，证明略。

以下为代码：

#include<bits/stdc++.h>
using namespace std;

const int N=114514,inf=INT_MAX;
const double eps=1e-9;

int n;
int a[N],b[N],c[N];
inline double f(double x){
    double maxn=-inf;
    for(int i=1;i<=n;i++){
        maxn=max(maxn,a[i]*x*x+b[i]*x+c[i]);
    }
    return maxn;
}

signed main() {
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i]>>b[i]>>c[i];
        }   

        double l=0,r=1000;
        while(r-l>eps){
            double m1=(2*l+r)/3;
            double m2=(l+2*r)/3;
            if(f(m1)<f(m2)){
                r=m2;
            }else{
                l=m1;
            }
        }

        cout<<fixed<<setprecision(4)<<f(l)<<endl;
    }
    return 0;
}