bzoj#P4051. [Cerc2013] History course
[Cerc2013] History course
题目描述
你被给定一系列关于重要的历史事件的演讲,每件事对应一场演讲。
它们不按顺序排列,每件历史事件持续一个时间段 。
如果两件事的时间有共同区间,我们说它们是有关联的,把关于有关联的历史事件的演讲排的彼此靠近能使课程更便于理解。
此外,不相关的演讲必须按历史事件的发生时间排序(如果 A 在 B 之前发生,且 AB 不相关,那么关于 A 的演讲必须在 B 之前进行)。
找出最小的整数 () 和一个演讲的顺序,使得排序后任意两场相关的演讲之间的间隔不超过 (第 场演讲和第 场演讲之间的间隔是 )。
输入格式
第一行包括数据组数 。
每组数据的第一行是一个数 ,接下来 行每行包括两个整数 ,区间两两不相同。
输出格式
每组数据答案的第一行是一个最小值 ,接下来 行按顺序列举排列后的演讲的历史区间(与输入中的格式一样),使得任意两个相关的演讲间隔不超过 。
切记将不相关的演讲按时间顺序排列!
1
3
1 6
2 3
4 5
1
2 3
1 6
4 5
样例说明
共有三个历史事件,其中 , 是相关的, 不相关,且 在 之前发生,所以 应该排在 的前面。
对于相关的历史事件, 与 在排列后的位置是 和 ,间隔为 , 与 在排列后的位置为 与 ,间隔为 ,所以此时 最小为 ,该排法最优。
数据规模与约定
对于 的数据,,。