C++: 宴会（banquet） - CSP-J2022 山东补测 - 优化后的代码实现与解题思路

C++: 宴会（banquet） - CSP-J2022 山东补测 - 优化后的代码实现与解题思路

题目来源: CF1730B 原题

题目描述:

一条纵向的街道上（相当于一维坐标）有 n 个人居住，其中第 i 个人居住在 x_i（非负整数）位置（坐标点）上。每月他们会选择在 x₀（数轴上的某一个点，不一定坐标点）处举办宴会。

已知第 i 个人从 x_i 出发前往宴会地点 x₀ 处需要花费 |x_i-x₀| 的时间，另外，他还需要花费 t_i 的时间进行打扮，换言之，他共需要花费 |x_i-x₀| + t_i 的时间到达宴会举办处。

假设初始时刻为 0。这 n 个人开始打扮和出发前往宴会处，他们想要使得宴会的开始时间尽可能早，于是向你求助，请你帮助他们确定好最优的宴会举办地点 x₀。

输入格式:

第一行一个正整数 T，表示测试数据的组数。

接下来对于每组测试数据（注意：每组测试数据有 3 行数据，以下共 3 T 行数据）：

• 第一行一个正整数 n，表示总官员人数。
• 第二行共 n 个非负整数 x₁,x₂,...,x_n 分别表示这 n 个人在数轴上的坐标。
• 第三行共 n 个非负整数 t₁,t₂,...,t_n 分别表示这 n 个人出发前的打扮时间。

输出格式:

共输出 T 行数据，对于每组测试数据，输出一行一个实数（如果是整数按整数输出，如果有小数，保留 1 位小数输出），表示使宴会开始时间最早的最优举办地点坐标 x₀。（很显然，x₀ 都是唯一的）

样例 #1

样例输入 #1:

7
1
0
3
2
3 1
0 0
2
1 4
0 0
3
1 2 3
0 0 0
3
1 2 3
4 1 2
3
3 3 3
5 3 3
6
5 4 7 2 10 4
3 2 5 1 4 6

样例输出 #1:

0
2
2.5
2
1
3
6

解题思路:

1. 最优宴会地点的判定: 对于每个参加者，到达宴会的总时间为 |x_i-x₀| + t_i。要使宴会开始时间最早，即需要找到一个 x₀，使得所有参加者到达宴会的时间最大值最小。
2. 找最大值最小: 这可以用二分法来解决，我们将 x₀ 的范围限定在所有参加者居住地点的最小值和最大值之间。对于每个二分的值 mid，我们可以计算出所有参加者到达 mid 的时间，并找到时间最大值。
3. 二分查找的边界: 每次二分查找，若当前最大到达时间大于上一次的最大到达时间，则说明 x₀ 需要向右移动，否则需要向左移动。

代码实现:

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int x[n], t[n];
        int minX = 1e9, maxX = -1e9;
        for (int i = 0; i < n; i++) {
            cin >> x[i];
            minX = min(minX, x[i]);
            maxX = max(maxX, x[i]);
        }
        for (int i = 0; i < n; i++) {
            cin >> t[i];
        }

        double left = minX, right = maxX;
        while (right - left > 1e-6) {
            double mid = (left + right) / 2.0;
            double maxTime = -1e9;
            for (int i = 0; i < n; i++) {
                maxTime = max(maxTime, abs(x[i] - mid) + t[i]);
            }
            if (maxTime > (left + right) / 2.0) {
                left = mid;
            } else {
                right = mid;
            }
        }
        printf('%.1lf
', (left + right) / 2.0);
    }
    return 0;
}

测试输入推理:

当 n = 1 时，只有一个参加者，最优的宴会地点就是该参加者的居住地点，因此 x₀ 等于 x₁。

总结:

本题主要考查了二分法的应用，通过二分查找找到最大到达时间最小的 x₀。代码实现较为简单，但需要理解二分法的原理以及最大值最小的概念。