聚会

GitHub跳转原题关系图返回列表

二分答案：时间 T 可行等价于每个人的可达区间有公共交点，判定只需比较区间左端点最大值与右端点最小值。

OJ: roj

题目 ID: 20027

难度:普及

标签:二分答案数学

创建: 2026-09-06 15:54

更新: 2026-10-07 13:50

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

数轴上有 nn 个人，第 ii 个人初始在 xix_i、速度 viv_i。选一个实数位置 pp 作为聚会点，所有人同时出发，求最晚到达时间的最小值 min⁡pmax⁡i∣xi−p∣/vi\min_{p} \max_{i} |x_i-p|/v_i。

输入第一行 nn，第二行 nn 个整数 xix_i，第三行 nn 个整数 viv_i；输出一个浮点数，四舍五入保留 5 位小数。样例：3 / 7 1 3 / 1 2 1 输出 2.00000。2≤n≤1052 \le n \le 10^5，1≤xi,vi≤1071 \le x_i, v_i \le 10^7。

思路

二分答案。给定时间 TT，第 ii 个人的可达区间是 [xi−viT, xi+viT][x_i-v_iT,\ x_i+v_iT]，所有人能同时到达等价于这些区间有公共交点，即左端点最大值 ≤\le 右端点最小值，一次判定 O(n)O(n) 且关于 TT 单调。实数二分约 100 次即可满足精度。

参考代码

cpp
/**
 * 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;
}