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

· · 题解

题目大意

给定街道的长度、每辆汽车的速度以及已经行驶的距离，求最先到达重点的汽车的编号。

解题思路

模拟。

设每辆汽车的速度为 v_i，已经行驶的距离为 x_i，总距离为 f，那么显然有每辆汽车还需要行驶的时间 t_i：

t_i = \frac{f - x_i}{v_i}

这样，我们就只需要找到 t_i 最小的 i 就可以了。

坑点

1. 要用 double，因为 f - x_i 并不一定是 v_i 的倍数。

2. 计算 t_i 的时候要用浮点数除法，不然即使 t_i 是 double 算出来也是整数。

AC Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100 + 5;
double t[MAXN];
signed main() {
    int n, f;
    cin >> n >> f;
    for (int i = 1; i <= n; i++) {
        int V, X;
        cin >> X >> V;
        t[i] = double(f - X) / V;
    }
    double Min = INT_MAX;
    for (int i = 1; i <= n; i++) {
        Min = min(Min, t[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (t[i] == Min) {
            cout << i;
            return 0;
        }
    }
    return 0;
}

时间复杂度 O(n)，空间复杂度 O(n)。