专栏文章

题解：CF2172B Buses

xxh39
CF2172B题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min2qhty
此快照首次捕获于
2025/12/01 19:36
3 个月前
此快照最后确认于
2025/12/01 19:36
3 个月前
查看原文
结论题。
题解中变量名与题面中有不同：s,t→l,r;  x,y→v0,v1;    l→cs,t\rightarrow l,r;\; x,y\rightarrow v_0,v_1;\;\;l\rightarrow c。

翻译（简化）

一条路长 cc。有 nn 辆均以 v0v_0 的速度向右匀速运动（即每秒向右走 v0v_0 单位长度）的列车，均在零时刻发车，第 ii 辆发自 lil_i 终于 rir_i。（位置 pp 表示距路左端点 pp。）
有 mm 人，第 ii 个人从位置 pip_i 出发到路右端点（位置 cc），可以 v1v_1 的速度行走，亦可乘车：若某时刻与某列车位置相同，则可上车；若已上车，可随时下车，但车到终点必须下车。（可不在整数时刻与位置上车。）
求出每个人到达终点的最短时间。以小数输出，要求相对相对误差或绝对误差小于 10−610^{-6} 。
数据范围：1≤n,m≤2×105,1≤c≤109,1≤v1<v0≤106;0≤li<ri<c,0≤pi≤c1\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 顺序连接构成完整的题解）
提示 0.0
所有的车速度一样。
提示 0.1
对每个人分析，他能上哪些列车？
解答 0
所有起点在位置 pp 之左（含 pp），终点位置在 pp 之右的列车都可搭乘。
即若 li≤pj<ril_i\le p_j<r_i，则第 jj 个人可搭乘列车 ii。
由于所有车平行运动（速度一样），所以不可能出现超车现象（乘一辆车追上另一辆车），于是在 pp 之右的列车，是不可能出现乘一辆车追上的。当然走路追就更不可能了。（v0>v1v_0>v_1）
所以只有起点在位置 pp 之左（含 pp）的列车可搭乘。
提示 1.0
车不等人，只会按照既定轨迹准时达到终点。
提示 1.1
结论：最多上一辆列车。想想为什么？
解答 1
假设要上两辆车，不如只上右边那辆车。因为无论上不上前一辆车，都能上后一辆车（所有在 pp 前的皆可上）。而无论是否上前一辆，到达终点的时间不变。
提示 2
求出若乘车 ii ，到达右端点 cc 的时间。
解答 2
显然坐车应该坐到终点，因为走路不如坐车快。
车走了 ri−lir_i-l_i 的路程，由速度公式，在 ri−liv0\dfrac{r_i-l_i}{v_0} 时刻到达终点。
之后走路，从 rir_i 到 cc，用时 c−riv1\dfrac{c-r_i}{v_1}。
相加，通分，总用时 (ri−li)v1+(c−ri)v0v0v1\dfrac{(r_i-l_i)v_1+(c-r_i)v_0}{v_0v_1}。
解答 3
在所有能坐上的车中，应选取一个用时最短的。
（易错点：还可以纯走路。用时 c−pjv1\dfrac{c-p_j}{v_1}。不过这个到输出结果时取最小值就好了。）
所以题目转换为了：有 mm 个询问，每个询问给出 pjp_j ，要在所有 li≤pj<ril_i\le p_j<r_i 的 ii 中求出 (ri−li)v1+(c−ri)v0v0v1\dfrac{(r_i-l_i)v_1+(c-r_i)v_0}{v_0v_1} 最小值。
提示 4.0
pj<rip_j<r_i 是否可以去掉？
解答 4.0
如果 pj≥rip_j\ge r_i，那么坐了这辆车，不仅用了时间，而且还退后了，肯定不优，会在取最小值时自动舍去，所以可以忽略 pj<rip_j<r_i 的条件。
提示 4.1
去掉这个条件后，越往右，能坐的车就越多。
提示 4.2
很自然地想到，给每个位置都记录最小乘车时间就好了。但这样会超时：c≤109c\le 10^9。
提示 4.3
记录必要的即可。
解答 4.3
显然，只有 lil_i 所在位置，才有可能导致能乘的车改变。所以只需要对于每个 ii，记录从 lil_i 出发最小乘车时间（不考虑纯走路所用的最短时间）。
遂按 lil_i 排序，从左到右依次求最小乘车时间。
设 zylizyl_i 表示从 li−1l_{i-1} 到 li−1l_{i}-1 这段区间内出发的点，最小乘车时间。可推出状态转移方程：zyl0=∞，zyli=min⁡(zyli−1,(ri−li)v1+(c−ri)v0v0v1)    (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)。（注：zyl0=∞zyl_0=\infin 是因为在 l0l_0 左边的乘不到车，这样与纯走路取 min⁡\min 时自动舍去。）
然后对每个人，二分查找最大的 ii 使 li<pjl_i<p_j 即可。（离线排序再双指针亦可。）

代码（C++）

为运算方便，将时间都乘以了 v0v1v_0v_1 以变成整数。最后输出时再除 v0v1v_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;
}
易错点：浮点数输出
printf("%f",...); 只会保留 66 位有效数字。本题要求误差在 10−610^{-6} 以内，所以会 WA。使用 "%.8f" 保留 88 位小数就能满足精度要求了。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...