信息学集训队作业drive

1、试题名称：Drive through MegaCity (drive)试题描述：平面上有个矩形，每个矩形的两边与坐标轴平行，且互不相交或者接触。汽车可以沿着与两坐标轴平行的方向行驶，平时驶过一个坐标需要10单位时间，而在某一个矩形内部驶过一个坐标需要时间，与矩形有关。求起点到终点最快需要多长时间。限制：矩形互不接触或交叉，起点和终点不在任何一个矩形内部或边上。思考：一种很容易想到的方法是按照水平纵横坐标离散，然后将每一条离散线与矩形的交点找出来构成关键点，最后使用Dijkstra+Heap算法求解。这一算法会产生个关键点与关键边，总复杂度为。遗憾的是这一复杂度的算法并不能通过本题。如果起点的横

2、坐标最小，终点的横坐标最大，则很明显最优路径的坐标是单调不降的，这样我们可以用一次从左到右的扫除来实现，时间复杂度仅为，且常数也较小。同样，如果起点的纵坐标最小，终点的纵坐标最大，则我们可以实现一次从下到上的扫除，时间复杂度同样仅为。幸运的是，我们可以证明无论起点与终点的位置如何，其最优路径一定只有这两种情况。这样我们可以在的时间内解决问题。事实上通过某种更加复杂的分治策略本题可以构造出规模的图，这样其实本题是存在复杂度的算法，但是的算法已经足以通过本题。算法介绍：性质1：在矩形内没有必要转向。 这一性质是显然的，因为矩形内部的任何转向操作都可以放到矩形外部进行而不会增大矩形内的通过里程。所以

3、这一性质说明我们只可能水平或者竖直“横穿”矩形。性质2：最优路径上的各点必有一维单调变化。 这个是本题的核心性质，下面我们尝试结合图形予以证明。图1 证明：不失一般性，假设（如图1所示）。任何其他情况可以通过旋转、对称等变化转化至这种情况。我们选择在一条不满足这一性质的路径中最先出现的“水平向左”这一操作。由于路径不满足性质，则在这一操作之前的运动中必然存在竖直的波动（如图1红色路迹线所示）图1图2图2图3(c)图3(c)图3(b)图3(b)图3(a)图3(a)显然，此时只可能出现图2所示的这种情况。图3(a)(c)解释了在其它情况下怎样找到一个更优或者相同优劣的解。（新的轨迹以红色虚线勾出）

4、。在图2这种情况下，我们试图找到一条“底层轮廓线”，在图4中用蓝色虚线勾出。这个底层轮廓线即沿着当前的矩形一直向左，然后竖直向上，直到遇到一个新的矩形的底部，然后再一直向左。由于所有的矩形互不相交或者接触，这条轮廓线上各点均能沿线不穿过矩形地直接到达目标点，并且所需代价仅为两点之间的曼哈顿距离（可能的最好代价）。因此，只要这条底层轮廓线与原轨迹（红色实线）相交，则通过这条线到达目标点一定是不劣的一个新解。而这条底层轮廓线本身的坐标是单调变化的。图5图4图5图4 当然，另一种可能是这条轮廓线与原来的轨迹并不相交，这时候只有一种可能，那就是如图5所示，底层轮廓线在坐标上已经到达了起点之左。这个时候

5、，我们考察底层轮廓线上方所有造成垂直波动的矩形，将从上方越过调整为从下方越过。这样，我们可以取消掉所有的垂直波动，尽管在水平方向上出现了波动。 这是因为，如果底层轮廓线所依附的矩形集合把整个下方封死，由于矩形之间不能相交或接触，其它的所有原轨迹绕过的矩形必然全部位于上方的位置。这样，调整绕过矩形的方向就有了意义。 因此，无论是图4还是图5，我们均能够找到一条满足性质的路径，这条路径至少不劣于原路径，因此本性质成立。（证毕）扫除算法。基于以上性质，我们设计如下的扫描算法。首先离散化所有的横纵坐标，然后，假设最优路线的横坐标单调，我们从一直扫描到（不妨设）。每一次扫描的时候做如下事情：（假设当前扫描线在）计算出相邻的两个离散线之间的距离代价从下到上，再从上到下两次更新当前最短路径。每次只更新相邻两点的最短路径。计算出与下一个离散线在各高度的距离代价，更新最短路径长度。计算距离代价的时候可以枚举个矩形然后直接暴力覆盖（i.e. 将该矩形覆盖的纵坐标范围内的所有离散线的运行时间全部赋值为）。这时假设最优路线横坐标单调时的扫除方法。纵坐标单调时只需要先交换所有点的纵横坐标再来做一次就可以了。最后答案就是两次结果的最小值。效率分析。 扫除过程共要考虑条离散线，每条离