自动搬运

查看原文

来自洛谷，原作者为

	Dangerise **

搬运于2025-08-24 21:31:27，当前版本为作者最后更新于2024-09-29 17:44:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

对一个定义域为 $(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,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;
}