题解：CF2172B Buses
xh39
·
2025-11-22 20:05:09
·
题解
结论题。
题解中变量名与题面中有不同：s,t\rightarrow l,r;\; x,y\rightarrow v_0,v_1;\;\;l\rightarrow c 。
翻译（简化）
一条路长 c 。有 n 辆均以 v_0 的速度向右匀速运动（即每秒向右走 v_0 单位长度）的列车，均在零时刻发车，第 i 辆发自 l_i 终于 r_i 。（位置 p 表示距路左端点 p 。）
有 m 人，第 i 个人从位置 p_i 出发到路右端点（位置 c ），可以 v_1 的速度行走，亦可乘车：若某时刻与某列车位置相同，则可上车；若已上车，可随时下车，但车到终点必须下车。（可不在整数时刻与位置上车。）
求出每个人到达终点的最短时间。以小数输出，要求相对相对误差或绝对误差小于 10^{-6} 。
数据范围：1\le n,m\le 2\times 10^5,1\le c\le 10^9,1\le v_1<v_0 \le 10^6;0\le l_i<r_i<c,0\le p_i\le c 。
题解
试试新渲染特性，以效 CF 题解之风。（注：建议按照数字 0、1、2、3、4 的顺序先点开提示，独立思考片刻。解答是该提示对应的步骤，解答 0、1、2、3、4 顺序连接构成完整的题解）
:::info[提示 0.0]
所有的车速度一样。
:::
:::info[提示 0.1]
对每个人分析，他能上哪些列车？
:::
:::success[解答 0]
所有起点在位置 p 之左（含 p ），终点位置在 p 之右的列车都可搭乘。
即若 l_i\le p_j<r_i ，则第 j 个人可搭乘列车 i 。
由于所有车平行运动（速度一样），所以不可能出现超车现象 （乘一辆车追上另一辆车），于是在 p 之右的列车，是不可能出现乘一辆车追上的。当然走路追就更不可能了。（v_0>v_1 ）
所以只有起点在位置 p 之左（含 p ）的列车可搭乘。
:::
:::info[提示 1.0]
车不等人，只会按照既定轨迹准时达到终点。
:::
:::info[提示 1.1]
结论：最多上一辆列车。想想为什么？
:::
:::success[解答 1]
假设要上两辆车，不如只上右边那辆车。因为无论上不上前一辆车，都能上后一辆车（所有在 p 前的皆可上）。而无论是否上前一辆，到达终点的时间不变。
:::
:::info[提示 2]
求出若乘车 i ，到达右端点 c 的时间。
:::
:::success[解答 2]
显然坐车应该坐到终点，因为走路不如坐车快。
车走了 r_i-l_i 的路程，由速度公式，在 \dfrac{r_i-l_i}{v_0} 时刻到达终点。
之后走路，从 r_i 到 c ，用时 \dfrac{c-r_i}{v_1} 。
相加，通分，总用时 \dfrac{(r_i-l_i)v_1+(c-r_i)v_0}{v_0v_1} 。
:::
::::success[解答 3]
在所有能坐上的车中，应选取一个用时最短的。
（易错点：还可以纯走路。用时 \dfrac{c-p_j}{v_1} 。不过这个到输出结果时取最小值就好了。）
所以题目转换为了：有 m 个询问，每个询问给出 p_j ，要在所有 l_i\le p_j<r_i 的 i 中求出 \dfrac{(r_i-l_i)v_1+(c-r_i)v_0}{v_0v_1} 最小值。
::::
:::info[提示 4.0]
:::
:::success[解答 4.0]
如果 $p_j\ge r_i$，那么坐了这辆车，不仅用了时间，而且还退后了，肯定不优，会在取最小值时自动舍去，所以可以忽略 $p_j<r_i$ 的条件。
:::
:::info[提示 4.1]
去掉这个条件后，越往右，能坐的车就越多。
:::
:::info[提示 4.2]
很自然地想到，给每个位置都记录最小乘车时间就好了。但这样会超时：$c\le 10^9$。
:::
:::info[提示 4.3]
记录必要的即可。
:::
:::success[解答 4.3]
显然，只有 $l_i$ 所在位置，才有可能导致能乘的车改变。所以只需要对于每个 $i$，记录从 $l_i$ 出发最小乘车时间（不考虑纯走路所用的最短时间）。
遂按 $l_i$ 排序，从左到右依次求最小乘车时间。
设 $zyl_i$ 表示从 $l_{i-1}$ 到 $l_{i}-1$ 这段区间内出发的点，最小乘车时间。可推出状态转移方程：$zyl_0=\infin，zyl_i=\min(zyl_{i-1},\dfrac{(r_i-l_i)v_1+(c-r_i)v_0}{v_0v_1})\;\;(i\ge1)$。（注：$zyl_0=\infin$ 是因为在 $l_0$ 左边的乘不到车，这样与纯走路取 $\min$ 时自动舍去。）
然后对每个人，二分查找最大的 $i$ 使 $l_i<p_j$ 即可。（离线排序再双指针亦可。）
:::
## 代码（C++）
为运算方便，将时间都乘以了 $v_0v_1$ 以变成整数。最后输出时再除 $v_0v_1$。
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
struct xyq{
int l,r;
}a[1000005];
struct rule{ //特殊比较方式。为了按照 $l$ 排序。
bool operator()(const xyq &s0,const xyq &s1){
return s0.l<s1.l;
}
};
long long zyl[1000005];
int main(){
int n,m,l,i,j;
long long v0,v1;
xyq tkr;
cin>>n>>m>>l>>v0>>v1;
for(i=0;i<n;i++){
scanf("%d %d",&a[i].l,&a[i].r);
}
sort(a,a+n,rule());
zyl[0]=2012345678987654321ll;
for(i=1;i<=n;i++){
zyl[i]=min(zyl[i-1],(a[i-1].r-a[i-1].l)*v1+(l-a[i-1].r)*v0);
}
for(i=0;i<m;i++){
scanf("%d",&tkr.l);
//下面一行，zyl[upper_bound(a,a+n,tkr,rule())-a] 是指最小的乘车时间，(l-tkr.l)*v0 是纯走路所用时间，两者取 min。
printf("%.8f\n",(double)min(zyl[upper_bound(a,a+n,tkr,rule())-a],(l-tkr.l)*v0)/(v0*v1)); //这里 upper_bound 是返回大于 tkr 的最小位置，返回值是一个指针，所以减去起始位置。大于 tkr 的前一个位置就是小于 tkr 的最大位置。由于 a 数组从 0 开始编号，本身就左移了 1 位，就不用再减一了。
}
return 0;
}
```
:::warning[易错点：浮点数输出]
```printf("%f",...);``` 只会保留 $6$ 位有效数字。本题要求误差在 $10^{-6}$ 以内，所以会 [WA](https://codeforces.com/contest/2172/submission/350146794)。使用 ```"%.8f"``` 保留 $8$ 位小数就能满足精度要求了。