p3406专题

【洛谷 P3406】海底高铁 题解(差分+前缀和+贪心算法)

海底高铁 题目描述 该铁路经过 N N N 个城市,每个城市都有一个站。不过,由于各个城市之间不能协调好,于是乘车每经过两个相邻的城市之间(方向不限),必须单独购买这一小段的车票。第 i i i 段铁路连接了城市 i i i 和城市 i + 1 ( 1 ≤ i < N ) i+1(1\leq i<N) i+1(1≤i<N)。如果搭乘的比较远,需要购买多张车票。第 i i i 段铁路购