CF2172B Buses 题解

sunqihuan · 2025-11-28 14:44:51 · 题解

有点诈骗的贪心题。因为车追不上人，所以只有在人前面的车可以上。并且只能上一辆车因为所有车的速度一样，相对位置也是固定的，上两辆车不如上后面那辆。因为车的速度大于人的速度所以选一辆车上然后步行到终点即可。求预处理前缀最大值，二分查询即可。

从其他题解学来一个小技巧，就是用含参数的二分函数，并且因为定义了比较器，所以其他的值可以不赋，只比较结构体中一个变量的值。

代码：

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 2e5 + 5;

int n, m, len, x, y, t[N];
struct Node
{
    int l, r;
}a[N];

bool cmp(Node p, Node q)
{
    return p.l < q.l;
}

signed main()
{
    cin >> n >> m >> len >> x >> y;
    for (int i = 1; i <= n; i ++ ) scanf("%lld%lld", &a[i].l, &a[i].r);
    sort(a + 1, a + n + 1, cmp);
    t[0] = 1e18;
    for (int i = 1; i <= n; i ++ ) t[i] = min(t[i - 1], (a[i].r - a[i].l) * y + (len - a[i].r) * x);
    while (m -- )
    {
        Node p;
        scanf("%lld", &p.l);
        int ans = min(t[upper_bound(a + 1, a + n + 1, p, cmp) - a - 1], (len - p.l) * x);
        printf("%.9lf\n", ans * 1.0 / (x * y * 1.0));
    }
    return 0;
}