1689. 旅游安排

单点时限: 2.0 sec

内存限制: 256 MB

在未来世界,大家出门都不是在地面走了,而是很方便的小飞船,而且大家要去的地方都是在空中的某个位置,即大家走的路线是个三维的 (x,y,z), 而且大家都是在飞船公司预约的飞船,由于飞船需要驾驶员,飞船使用费用等等,为了使成本最低,飞船公司尽量安排最少的飞船去满足大家的需要,即一个飞船能在下一个预约人的时间之前 (可以等于) 到达这个人的起始位置就可以接着使用这个飞船。但是预约的执行顺序不变,飞船每走一个坐标值需要 1 单位时间 (abs(x1-x2)+abs(y1-y2)+abs(z1-z2) == 1),即需要时间 1。而且飞船不是按照直线走的,而是要么顺着 x,要么顺着 y,要么顺着 z 走。

输入格式

输入一个 n,(0<n<1000), 表示预约的个数,接下来 n 行,每行 (t,x1,y1,z1,x2,y2,z2) 表示预约人的情况,t 表示这个人需要在时间 t 使用飞船,(x1,y1,z1) 表示他开始的位置,(x2,y2,z2) 表示他要去的目的地。

输入都是整数。多组数据。

输出格式

输出一个数 m,表示最少需要 m 个飞船

样例

Input
1
1 1 1 1 2 2 2
Output
1

3 人解决,14 人已尝试。

3 份提交通过,共有 92 份提交。

9.4 EMB 奖励。

创建: 16 年,7 月前.

修改: 6 年,8 月前.

最后提交: 3 年,5 月前.

来源: LSP

题目标签