搬桌子

TimeLimit:1000ms MemoryLimit:128000KB

64-bit integer IO format:%lld

未提交 | 登录后收藏

Problem Description

过道
1	2	.........	99	100

在教学楼里面有 100 间教室连成一排，以一个过道连接，如上图，每一间教室里面都有桌子，现在学校打算将桌子从教室里面移动到其他教室去，但是过道只能允许一个桌字通过，两个桌子并排是通不过的。不论桌子移动的距离多长，都只花一个单位的时间就可以到达指定的教室，有些桌子的移动是可以同时进行的（如下表）。管理者想要知道桌子移动完最短需要多少时间。

可以	30 ->50 和 60->90	没有共有部分
可以	11->12 和 14->13	没有共有部分
不可以	1->4 和 3->6	3 、 4号房间共有
不可以	1->2 和 2 ->3	2号房间共有

值得注意的是操作1->2 和 2->3操作并不化简为 1->3 的操作，因为每个桌子都是有编号的。

Input

输入n表示案例数<=10，输入m表示即将输入的个数<=100。
接下来输入m行每一行都有a,b两个整数代表教室编号（1<=a,b<=100）

Output

输出搬完桌子的最少耗时多少个单位时间。
具体的输出格式”Case #i: k”,其中i 是第i个案例，k是该案例中最短的耗时，每个案例一行。

SampleInput

SampleOutput

Case #1: 1
Case #2: 2
Case #3: 3

Submit

题目统计信息详细


总AC数	11
通过人数	9
尝试人数	12
总提交量	48
AC率	18.75%

标签——1744

name	rating
基础	5296
暴力	1129
预处理优化	1129
线段树	536
贪心	466

AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题，请不要查看标签
如果您已经通过了该题，请务为该题贴上标签

出处

【FJUT】第三届新生赛真题

搬桌子

T^T Online Judge