聚会 - 题目列表

形式化题目

数轴上有 $n$ 个人，第 $i$ 个人初始在 $x_i$ ，移动速度为 $v_i$ 。选一个实数位置 $p$ 作为聚会点（不要求是整数），所有人同时出发，求"最晚到达者"的到达时间的最小值：

\min_{p \in \mathbb{R}}\ \max_{1 \le i \le n}\ \frac{|x_i - p|}{v_i}

思路

一句话本质：“最小化最晚到达时间"反过来变成"判定给定时间 $T$ 内能否全部赶到”——每人可达区间 $[x_i - v_iT,\ x_i + v_iT]$ 的交非空，判定 $O(n)$ 且关于 $T$ 单调，于是二分答案。

先看一个可以直接验证想法的小数据精确解：

cpp

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-06 15:54
 * update_at: 2026-09-06 16:00
 */
// brute.cpp：小数据暴力解，枚举全部候选聚会点，精确求出 f(p) 的最小值。
// f(p) = max_i |x_i - p| / v_i 是凸函数，最小值出现在两个 V 形的交点、
// 区间端点或某个 x_i 处，因此枚举这些候选点即可得到精确最小值。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n;
double x[MAXN], v[MAXN];

// 计算在点 p 聚会时，最晚到达的时间。
double f(double p) {
    double t = 0;
    for (int i = 1; i <= n; i++) {
        t = max(t, fabs(x[i] - p) / v[i]);
    }
    return t;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> x[i];
    for (int i = 1; i <= n; i++) cin >> v[i];

    double minx = x[1], maxx = x[1];
    for (int i = 2; i <= n; i++) {
        minx = min(minx, x[i]);
        maxx = max(maxx, x[i]);
    }

    vector<double> cand; // 候选聚会点
    cand.push_back(minx);
    cand.push_back(maxx);
    for (int i = 1; i <= n; i++) cand.push_back(x[i]);

    // 枚举每对 V 形函数的交点，三种位置关系各解一次方程。
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            // 两人同侧（p 在两者同一边）：p = (v_j x_i - v_i x_j) / (v_j - v_i)
            if (fabs(v[j] - v[i]) > 1e-12) {
                cand.push_back((v[j] * x[i] - v[i] * x[j]) / (v[j] - v[i]));
            }
            // 两人异侧（p 在两者之间）：p = (v_j x_i + v_i x_j) / (v_i + v_j)
            cand.push_back((v[j] * x[i] + v[i] * x[j]) / (v[i] + v[j]));
        }
    }

    double ans = 1e18;
    for (double p : cand) {
        if (p < minx || p > maxx) continue; // 最优聚点一定在坐标范围内
        ans = min(ans, f(p));
    }

    printf("%.5f\n", ans);
    return 0;
}

这个暴力直接枚举候选聚会点： $f(p)=\max_i |x_i-p|/v_i$ 是 $n$ 个 V 形函数的最大值，仍为凸函数，最小值一定出现在两个 V 形的交点、区间端点或某个 $x_i$ 处。枚举全部 $O(n^2)$ 个候选点、每个 $O(n)$ 求值，实运算下是精确解，只适合 $n \leqslant 5$ 的小数据。

问题？ 直接求最优位置难在哪？

$p$ 是实数，无法枚举；候选点 $O(n^2)$ 个、每个求值 $O(n)$ ， $n=10^5$ 时不可行。

问题？ 换个角度，怎么判定"给定时间 $T$ 能不能赶到"？

第 $i$ 个人在时间 $T$ 内最远能走到 $x_i - v_iT$ 和 $x_i + v_iT$ ，这之间的位置都能到，即可达区间 $[x_i - v_iT,\ x_i + v_iT]$ 。所有人能同时到达 ⟺ 存在一个点 $p$ 属于所有人的区间 ⟺ 这些区间的交非空。

问题？ 区间交非空怎么快速判断？

$n$ 个区间的交非空 ⟺ 所有左端点的最大值 ≤ 所有右端点的最小值。设 $L=\max_i(x_i - v_iT)$ 、 $R=\min_i(x_i + v_iT)$ ，可行当且仅当 $L \le R$ 。一次判定 $O(n)$ 。

问题？ 判定和答案有什么关系，为什么能二分？

“ $T$ 可行"关于 $T$ 单调：时间越长，每个人的可达区间越宽，交只会越来越"满”。所以可以用二分找出最小的可行 $T$ 。上界取坐标跨度（速度至少为 1，时间不会超过跨度），二分约 100 次，精度远高于 $10^{-5}$ 。

下面这张表用样例 #1（ $x=[7,1,3]$ ， $v=[1,2,1]$ ）展示 $T=2$ 时的判定：

人	初始位置	速度	可达区间 $[x_i - v_iT, x_i + v_iT]$
1	7	1	$[5, 9]$
2	1	2	$[-3, 5]$
3	3	1	$[1, 5]$

看三个区间的交：左端点最大是 $5$ （人 1 的左端点），右端点最小是 $5$ （人 2、3 的右端点）， $5 \le 5$ 交非空，公共点是 $p=5$ 。若 $T < 2$ ，人 1 的左端点 $7-T > 5$ 超过人 2 的右端点 $1+2T < 5$ ，交为空，所以最小时间正是 2。

问题？ 二分结束时输出什么？

二分把可行区间压到 $[lo, hi]$ ，结束时 lo 即最小可行时间的近似值，误差 $< 10^{-9}$ ，用 printf("%.5f") 四舍五入保留 5 位小数即可。

代码

cpp

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-06 15:54
 * update_at: 2026-09-06 16:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const double EPS = 1e-9;

int n;
double x[MAXN], v[MAXN];

// 判断时间 T 内所有人能否赶到同一个点：
// 第 i 个人的可达区间是 [x_i - v_i*T, x_i + v_i*T]，
// 所有人能同时到达当且仅当这些区间的交非空。
bool check(double T) {
    double l = -1e18, r = 1e18;
    for (int i = 1; i <= n; i++) {
        l = max(l, x[i] - v[i] * T); // 所有区间左端点的最大值
        r = min(r, x[i] + v[i] * T); // 所有区间右端点的最小值
    }
    return l <= r + EPS;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    double minx = 1e18, maxx = -1e18;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        minx = min(minx, x[i]);
        maxx = max(maxx, x[i]);
    }
    for (int i = 1; i <= n; i++) cin >> v[i];

    // 二分答案：时间 T 可行具有单调性。
    double lo = 0, hi = maxx - minx; // 速度至少为 1，时间上界取坐标跨度
    for (int step = 0; step < 100; step++) {
        double mid = (lo + hi) / 2;
        if (check(mid)) hi = mid;
        else lo = mid;
    }

    printf("%.5f\n", lo);
    return 0;
}

复杂度

时间：每次判定 $O(n)$ ，二分 100 次，总 $O(100n) = O(n)$ 。
空间： $O(n)$ 。

总结

核心转化（正难则反）：求最优位置困难，改为"给定时间 $T$ 判定可行性"，把优化问题变成判定问题。
核心判定：可达区间 $[x_i - v_iT, x_i + v_iT]$ 的交非空 ⟺ 左端点最大值 ≤ 右端点最小值，一次扫描 $O(n)$ 。
可迁移思想："最小化最大值"且判定具有单调性的题，直接二分答案；实数二分固定迭代次数（如 100 次）控制精度，比比较 hi-lo 更省心。

聚会

目录

形式化题目

思路

代码

复杂度

总结