YBT高效进阶 4.6.2 洛谷P1081 开车旅行 TITLE 题目描述 小A和小B决定利用假期外出旅行，他们将想去的城市从1到n编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市i的海拔高度为h_i城市i和城市j之间的距离d_{i,j},恰好是这两个城市海拔高度之差的绝对值，即 d i , j = ∣ h i − h j ∣ d_{i,j}=|h_i-

题目链接 分析 感觉这题有紫啊。 朴素的思路，预处理路程，暴力枚举会到那个城市，然后直接模拟整个过程。显然超时，复杂度 O ( ( n + m ) ∗ n 2 ) O((n+m)*n^2) O((n+m)∗n2)。 换思路，首先，可以发现，对于某个已知的城市，且已经确定是小A/小B开车，那下一步的终点城市是唯一的。而且无论哪个询问，只要能在规定时间内求出以 s i s_i si​