洛谷 P1883——函数 题解

题目

题目描述

给定 n n n 个二次函数 f 1 ( x ) , f 2 ( x ) , … , f n ( x ) f_1(x),f_2(x),\dots,f_n(x) f1(x),f2(x),,fn(x)(均形如 a x 2 + b x + c ax^2+bx+c ax2+bx+c),设 F ( x ) = max ⁡ { f 1 ( x ) , f 2 ( x ) , . . . , f n ( x ) } F(x)=\max\{f_1(x),f_2(x),...,f_n(x)\} F(x)=max{ f1(x),f2(x),...,fn(x)},求 F ( x ) F(x) F(x) 在区间 [ 0 , 1000 ] [0,1000] [0,1000] 上的最小值。

输入格式

输入第一行为正整数 T T T,表示有 T T T 组数据。

每组数据第一行一个正整数 n n n,接着 n n n 行,每行 3 3 3 个整数 a , b , c a,b,c a,b,c,用来表示每个二次函数的 3 3 3 个系数,注意二次函数有可能退化成一次。

输出格式

每组数据输出一行,表示 F ( x ) F(x) F(x) 的在区间 [ 0 , 1000 ] [0,1000] [0,1000] 上的最小值。答案精确到小数点后四位,四舍五入。

样例 #1

样例输入 #1

2
1
2 0 0
2
2 0 0
2 -4 2

样例输出 #1

0.0000
0.5000

提示

对于 50 % 50\% 50% 的数据, n ≤ 100 n\le 100 n100

对于 100 % 100\% 100% 的数据, T < 10 T<10 T<10   n ≤ 1 0 4 \ n\le 10^4  n104 0 ≤ a ≤ 100 0\le a\le 100 0a100 ∣ b ∣ ≤ 5 × 1 0 3 |b| \le 5\times 10^3 b5×103 ∣ c ∣ ≤ 5 × 1 0 3 |c| \le 5\times 10^3 c5×103

题目分析

题目目的是求出对于每一个x的取值,所有的fi(x)(<=i<=n)的值的最大值记为F(x),即 F(x)=max{f1(x),f2(x),……,fn(x));,题目最终要求的是F(x)在[0,1000]的区间内的最小值

难点

我们知道,函数F(x)在区间内一定具有一个连续的函数图像,但是具体的函数图像单调性并不太清楚,到底是单调增还是减,又或者是抛物线形状,又或者是其他,清楚函数的单调性,决定了我们究竟选用二分法还是三分法来求这个最值。

又由提示可知,a>=0,所以f(x)的函数图像一定是下凹函数或者单调递增递减函数。

接下来,我用一幅图,很清晰的让大家看到函数F(x)的单调性是如何的:
在这里插入图片描述
具体的微积分证明不加以阐述

从图中我们不难看出,F(x)函数为下凹函数,所以可以使用三分法来寻找区间内的最大值。

完整代码

#include<iostream>
using namespace std;
const double eps = 1e-9;     //精度一定要高,不然真的会出事。
int t;                         //eps的类型一定要是double,如果是int的话,死循环GG
int n;
int a[10005];
int b[10005];
int c[10005];
double check(double x) {
   
	double MAX =-(1e+4);
	for (int i = 1; i <= n; i++) {
   
		MAX = max(MAX, a[i] * x * x + b[i] * x + c[i]);
	}
	return MAX;
}
int main() {
   
	cin >> t;
	while (t--) {
   
		cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> a[i] >> b[i] >> c[i];
		double l = 0.0;
		double r = 1000.0;
		while (r - l > eps) {
   
			double k = (r - l) / 3.0;
			double mid1 = l + k;
			double mid2 = r - k;
			if (check(mid1) > check(mid2))
				l = mid1;
			else
				r = mid2;
		}
		printf("%.4f", l);
	}
	return 0;
}