信息学奥赛一本通 1435：【例题3】曲线 | 洛谷 洛谷 P1883 函数

【题目链接】

ybt 1435：【例题3】曲线
洛谷 P1883 函数

【题目考点】

1. 三分

【解题思路】

每个$S_i(x)$是一个二次函数，$F(x)=max(S_i(x))$，即为所有二次函数当自变量为x时的所有函数值的最大值。
已知$a\ge 0$，所以所有的二次函数都是开口向上的，为下凸函数。
首先要证明$F(x)$在定义域为[0, 1000]的范围内是下凸函数（凸函数定义）

已知f(x),g(x)为下凸函数，证明h(x)=max(f(x),g(x))是一个下凸函数。
证明:
根据凸函数的定义，对于任意的$0\le \alpha \le 1$，定义域内的任意$x1,x2$，总有
$f(\alpha x1+(1-\alpha )x2)\le \alpha f(x1)+(1-\alpha )f(x2)\le \alpha h(x1)+(1-\alpha )h(x2)$
同理，对于g(x)也有相似的结论：
$g(\alpha x1+(1-\alpha )x2)\le \alpha g(x1)+(1-\alpha )g(x2)\le \alpha h(x1)+(1-\alpha )h(x2)$

将$x=\alpha x1+(1-\alpha )x2$带入$h(x)$，有
$h(\alpha x1+(1-\alpha )x2)=max(f(\alpha x1+(1-\alpha )x2),g(\alpha x1+(1-\alpha )x2))\le max(\alpha h(x1)+(1-\alpha )h(x2),\alpha h(x1)+(1-\alpha )h(x2))=\alpha h(x1)+(1-\alpha )h(x2)$
h(x)满足下凸函数的定义，因此也是下凸函数

已知f(x),g(x)两个函数的较大值h(x)=max(f(x),g(x))是下凸函数，那么多个函数的最大值$F(x)$也是下凸函数。

已知$F(x)$在定义域[0,1000]中是下凸函数（单谷函数），因此可以使用三分求单谷函数的极小值点。
首先把左端点l设为0，右端点r设为1000
每次循环取三分点lm = l+(r-l)/3, rm = r-(r-l)/3
求出两个三分点位置的函数值f(lm)、f(rm)
设极值点为m（注：极值点是取到极值时函数自变量的值）

• 当f(lm)r = rm，[l, r]的范围缩减1/3。
• 当f(lm)>f(rm)时，可能是lm < m < rm，或lm > rm > m，极值点一定不在[l, lm]的范围内，因此使l = lm，[l, r]的范围缩减1/3。
  当$r-l<10^{-10}$时，跳出循环，此时l或r都是极值点的近似值。
  求极值点位置的函数值，即为$f(l)$

三分算法的时间复杂度：$O(logn)$，n为初始的数值范围大小，在本题中为1000。
【注】：r与l差值很小时结束循环，对于一般的结果保留几位小数的问题（比如保留5位，8位等），将差值取为$10^{-10}$是合理的。取$r-l<10^{-10}$与取$r-l<10^{-5}$在循环次数上是相同数量级的，而且能保证结果的准确性。

【题解代码】

解法1：三分

#include
using namespace std;
#define N 10005
int a[N], b[N], c[N], n, t;//a[i], b[i], c[i]：第i个二次函数的a、b、c
double f(double x)
{
	double ans = -1e9;
	for(int i = 1; i <= n; ++i)
		ans = max(ans, a[i]*x*x+b[i]*x+c[i]);
	return ans;
}
int main()
{
	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;
		while(r-l >= 1e-10)
		{
			double lm = l+(r-l)/3, rm = r-(r-l)/3;
			if(f(lm) > f(rm))
				l = lm;
			else
				r = rm;
		}
		printf("%.4f\n", f(l));
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32