走廊调度问题 - 最小化移动桌子的时间

走廊调度问题 - 最小化移动桌子的时间

问题描述

著名的ACM（高级计算机制造商）公司租赁了一栋楼的一层，该楼层有200个房间，分别位于走廊的北侧和南侧。最近，公司制定了一个改革计划，其中包括在房间之间移动许多桌子。由于走廊很窄，而且所有的桌子都很大，所以一次只能通过一个桌子通过走廊。为了提高效率，公司需要制定一个合理的移动计划，以最小化移动所有桌子的总时间。

任务描述

你的任务是编写一个程序，帮助ACM公司解决这个调度问题。

移动规则:

• 从一个房间移动一张桌子到另一个房间可以在10分钟内完成。* 当从房间 i 移动桌子到房间 j 时，会占用从房间 i 前面到房间 j 前面的走廊部分。* 在每10分钟内，可以同时进行多个不共享走廊相同部分的房间之间的移动。* 对于每个房间，最多只能移入或移出一张桌子。

输入格式

输入由 T 个测试用例组成。

• 第一行给出了测试用例的数量 T。* 每个测试用例以一行包含一个整数 N (1 <= N <= 200) 开始，表示要移动的桌子数量。* 接下来的 N 行中，每行包含两个正整数 s 和 t，表示要将一张桌子从房间编号 s 移动到房间编号 t （每个房间号在 N 行中最多出现一次）。* 从第 N+3 行开始，以与上述相同的方式列出剩余的测试用例。

输出格式

输出应该包含每个测试用例的最小完成移动时间（以分钟为单位），每行一个。

示例

输入:

1310 2030 4050 60

输出:

10

解释:

在这个例子中，只有一个测试用例，需要移动 3 张桌子。由于这 3 次移动不会占用走廊的相同部分，因此可以同时进行，总共只需要 10 分钟。

提示

• 可以将这个问题看作一个图论问题，其中房间是节点，走廊部分是边。* 可以使用贪心算法或图论算法来解决这个问题。