题解：P13347 「ZYZ 2025」地铁

alst_1 · 2025-07-20 21:35:53 · 题解

AC代码：

include<bits/stdc++.h>

using namespace std;

struct Bus {

int t, v;

};

bool compareBuses(const Bus& a, const Bus& b) {

return a.v > b.v; // 按速度从快到慢排序

}

int main() {

int n, S, E, v0;

cin >> n >> S >> E >> v0;

vector<Bus> buses(n);

for (int i = 0; i < n; ++i) {

    cin >> buses[i].t >> buses[i].v;

}

// 按速度从快到慢排序
sort(buses.begin(), buses.end(), compareBuses);

double min_time = (double)(E - S) / v0; // 纯步行时间

double current_pos = S;

double current_time = 0.0;

for (const auto& bus : buses) {

    if (bus.v <= v0) continue; // 公交车不比步行快，不考虑

    // 计算小Q步行到与公交车相遇的位置和时间
    // 设相遇时间为t_meet，位置为x
    // x = bus.v * (t_meet - bus.t)
    // x = current_pos + v0 * (t_meet - current_time)
    // 解方程：

    double t_meet = (bus.v * bus.t + current_pos - v0 * current_time) / (bus.v - v0);
    double x = bus.v * (t_meet - bus.t);

    if (x < current_pos) continue; // 公交车已经开过

    // 更新当前位置和时间
    current_pos = x;
    current_time = t_meet;

    // 计算从当前位置到终点的时间
    double remaining_time = (double)(E - current_pos) / bus.v;
    double total_time = current_time + remaining_time;

    if (total_time < min_time) {
        min_time = total_time;
    }
}

cout << fixed << setprecision(5) << min_time << endl;
return 0;

}