问题 6186. -- NOI2013湖北省选 一试 第3题 旅行

6186: NOI2013湖北省选 一试 第3题 旅行

时间限制: 1 Sec  内存限制: 512 MB
献花: 0  解决: 0
[献花][花圈]

题目描述

在遥远的HX 国,住着一个旅行家小L,他希望骑着他的自行车游遍全国。在这个国家中,每个城市都有一个编号,共有n 个城市,编号从1 到n。有的城市没有小L 想去的景点,而有的城市有且仅有一个小L 想去的景点,所有城市都是这两种情况之一。小L 非常热爱信息学,他编写程序给他的旅行安排了一条最短路线以到达所有他想去的景点(所以他旅行线路上城市编号是乱序的):他第1 个到达的城市编号为a1,第i 个到达的城市编号为ai,最后到达城市an 结束这次旅行。小L 希望用恰好m 个月(m < n)的时间完成这次旅行,所
以他需要制定一个理性的旅行计划。
当他到达一个城市时,如果这个城市有他想要去的景点,他会因此获得1 点快乐值;但
是若到达的城市没有他想去的景点,他会因旅途的疲惫得到1 点疲劳值。一个月的时间足够
他游玩任意多个城市,但他也希望拿出一定时间来休息。他每个月总是在本月所达到的最后
一个城市休息(但如果这个城市有景点,那么小L 总会游玩完这个景点再休息)。当然,小
L 希望每个月都能有一定的旅行任务,即便这个月他所到达的城市中并没有他想去的景点,
换句话说,每个月他都会至少到达一个新的城市。
小L 无法自己安排旅行计划,所以求助于你。你需要告诉他一个序列:
x1, x2, …, xm
xi 表示小L 第i 个月休息时,他所在的城市编号。由于他最后一个月必须完成他的旅行,
所以xm 肯定等于an。例如,设n = 5,m = 3,(a1, a2, a3, a4, a5) = (3, 2, 4, 1, 5),(x1, x2, x3) = (2,
1, 5),这意味着:第1 个月先后到达3 号和2 号城市,并在2 号城市休息;第2 个月先后到
达4 号和1 号城市,并在1 号城市休息;第3 个月到达5 号城市,并在5 号城市休息。
这样的方案序列有很多种,设每种方案序列中的第i 个月旅行中当月获得的快乐值与疲
劳值的差的绝对值为di,设第k 种方案序列中求出的d1, d2, …, dm这个m个值的最大值为ck,
小L 希望所选择的方案序列的ck 在所有方案序列中是最小的。
事实上,可能有多个方案序列的ck 达到并列最小值。由于小L 喜爱编程,他患上了一
定的强迫症(虽然他自己认为他的强迫症让他炫的发黄),他希望给他的序列是这多个方案
中字典序最小的。。
Tips:比较两个序列字典序即比较第一个不相同数字的大小,如1, 2, 3, 4 < 1, 2, 4, 3。

输入

第一行为两个空格隔开的正整数n, m,表示旅行的城市数与旅行所
花的月数。
接下来n 行,其中第i 行包含两个空格隔开的整数ai 和bi,ai 表示他第i 个去的城市编
号;bi 为0 或1:如果bi 为0,则表示城市ai 没有小L 想去的景点,若为1 则表示城市ai
有小L 想去的景点。

ai 两两不同且有1 ≤ ai ≤ n,即{ai}为1, 2, …, n 的一个排列,例如{2, 1, 3, 4, …, n}。


对于10%的数据,n ≤ 10;
对于25%的数据,m ≤ 10;
对于30%的数据,n ≤ 100;
对于40%的数据,m ≤ 100;
对于40%的数据,n ≤ 1000;
对于55%的数据,n ≤ 180000;
对于100%的数据,n ≤ 500000,m ≤ 200000。

输出

仅包括一行,包含m 个空格隔开的正整数x1, x2, …, xm,为给小L 安排旅行计划对应的路线。


【输入输出样例1】
input         output
8 3             1 6 8
2 0
3 1
4 1
1 0
5 0
6 1
7 1
8 0
【样例解释1】
第1 个月得到2 点快乐值与2 点疲劳值,第2 个月得到1 点快乐值与1 点疲劳值,第3
个月得到1 点快乐值与1 点疲劳值。3 个月中疲劳值与快乐值差的最大值为0,达到所有方
案最小值。
可行方案有:
1 6 8
3 6 8
3 1 8
其中1 6 8 字典序最小。
【输入输出样例2】
input         output
8 6             2 1 5 6 7 8
2 0
3 1
4 1
1 0
5 0
6 1
7 1
8 0
【样例解释2】
6 个月中每个月获得的疲劳值与快乐值差均为1,所以差的最大值为1,达到所有方案
最小值。

样例输入

8 3
2 0
3 1
4 1
1 0
5 0
6 1
7 1
8 0

样例输出

1 6 8

提示

来源

[献花][花圈]