题解：P15639 [ICPC 2022 Tehran R] Flower Festival

GTXxg · 2026-03-07 10:33:51 · 题解

有 n 辆车在一条长度为 f 的直线上向终点（玫瑰广场，位置 f）行驶。第 i 辆车当前在位置 x_i（距起点），以恒定速度 v_i 前进。到达时间 t_i = \dfrac{f - x_i}{v_i}。保证没有并列最早到达的车。

求最先到达（t_i 最小）的车辆编号。

直接计算每辆车到终点的剩余距离 d_i = f - x_i，时间可用 \dfrac{d_i}{v_i} 比较。

为避免浮点误差，对两车 i 和 j，比较 \dfrac{d_i}{v_i} 和 \dfrac{d_j}{v_j} 等价于比较 d_i \times v_j 与 d_j \times v_i。

遍历 O(n)，维护当前最小时间对应的车即可。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, f;
    cin >> n >> f;
    int maxid = -1,maxd = 1, maxv = 1; 
    for (int i = 1; i <= n; ++i) {
        int x, v;
        cin >> x >> v;
        int d = f - x; // 剩余距离
        if (maxid == -1) {
            maxid = i; maxd = d; maxv = v;
        } else {
            // 比较 d/v 与 maxd/maxv：d * maxv < maxd * v 则更早到达
            if (1LL * d * maxv < 1LL * maxd * v) {
                maxid = i;
                maxd = d;
                maxv = v;
            }
        }
    }
    cout << maxid << '\n';
    return 0;
}