A23 三分小数 • EH's Blog

题目情境#

题目链接：https://www.luogu.com.cn/problem/P1883 ↗

题目描述

给定 $n$ 个二次函数 $f_1(x),f_2(x),\dots,f_n(x)$ （均形如 $ax^2+bx+c$ ），设 $F(x)=\max\{f_1(x),f_2(x),...,f_n(x)\}$ ，求 $F(x)$ 在区间 $[0,1000]$ 上的最小值。

输入格式

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

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

输出格式

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

输入输出样例

输入 #1

plaintext

输出 #1

0.0000
0.5000

plaintext

对于 $100\%$ 的数据， $T<10$ ， $n\le 10^4$ ， $0\le a\le 100$ ， $|b| \le 5\times 10^3$ ， $|c| \le 5\times 10^3$ 。

算法解析#

本题求的是若干二次函数上包络线 $F(x)=\max_i f_i(x)$ 在区间 $[0,1000]$ 的最小值。

对每个固定的 $x$ ， $F(x)$ 是若干二次函数值中的最大者，因此 $F(x)$ 本身是一个凸函数。我们可以在区间上使用三分法（Ternary Search）寻找最小值：

保持区间 $[l,r]$ ，取两个三分点 $m_1=(2l+r)/3$ 和 $m_2=(l+2r)/3$ ；
计算 $F(m_1)$ 和 $F(m_2)$ ；
若 $F(m_1) < F(m_2)$ ，说明最小值在左半区间，令 $r=m_2$ ；否则令 $l=m_1$ ；
反复收窄区间直到区间足够小，然后取当前点近似最小值。

注意本题的函数是浮点连续的，使用三分法可以在精度范围内快速逼近最优解。

Python代码实现#

import sys
import math

INF = float('inf')
EPS = 1e-9

def f(x, n, a, b, c):
    maxn = -INF
    for i in range(n):
        val = a[i] * x * x + b[i] * x + c[i]
        maxn = max(maxn, val)
    return maxn

t = int(input())
for _ in range(t):
    n = int(input())
    a = []
    b = []
    c = []
    for _ in range(n):
        ai, bi, ci = map(int, input().split())
        a.append(ai)
        b.append(bi)
        c.append(ci)

    l = 0.0
    r = 1000.0
    while r - l > EPS:
        m1 = (2 * l + r) / 3
        m2 = (l + 2 * r) / 3
        if f(m1, n, a, b, c) < f(m2, n, a, b, c):
            r = m2
        else:
            l = m1
    print(f"{f(l, n, a, b, c):.4f}")

python

C++代码实现#

#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;
}