题解：P12261 [蓝桥杯 2024 国 Java B] 激光炮

W_C_B_H · 2025-04-20 19:27:45 · 题解

设一次函数 f_i(x)=p_ix+q_i 经过点 (-10^5,a_i) 和 (10^5,b_i)，则有：

解得：

设 \begin{aligned}f(x)=\max_{1\le i\le n}f_i(x)\end{aligned}，则答案即为 -10^5\le x\le 10^5 时，f(x) 的最小值。

观察可得，f(x) 有且仅有这三种情况：

• 在 [-10^5,10^5] 上单调不降。

• 在 [-10^5,10^5] 上单调不增。

• 存在 -10^5 < x < 10^5，使得 f(x) 在 [-10^5,x] 上单调不增，在 [x,10^5] 上单调不降。

所以我们可以用三分算法求出 f(x) 的最小值。

Code：

import java.util.Scanner;
public class Main {
    static final int N = 100005;
    static final double eps = 1e-3;
    static int n;
    static double[] p = new double[N], q = new double[N];
    static double f(double x) {
        double ret = 0d;
        for(int i = 1; i <= n; i++) {
            ret = Math.max(ret, p[i] * x + q[i]);
        }
        return ret;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        for(int i = 1; i <= n; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            p[i] = (b - a) / 2e5;
            q[i] = (a + b) * 0.5;
        }
        double l = -1e5, r = 1e5, mid1, mid2;
        while(r - l > eps) {
            mid1 = l + (r - l) / 3;
            mid2 = r - (r - l) / 3;
            double f1 = f(mid1), f2 = f(mid2);
            if(f1 < f2) {
                r = mid2;
            } else {
                l = mid1;
            }
        }
        System.out.printf("%.2f", f(l));
        sc.close();
    }
}