分数: 700 点
问题陈述
给你一个正整数 N 和长度为正整数的序列 N: L=(L_1,L_2,\ldots,L_N),R=(R_1,R_2,\ldots,R_N)。可以保证 L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N 都是不同的。
一家电影院有 N 座位从左到右排列成一排。的 i从左边算起第一个座位称为座位 i.
N 人,已编号 1 to N,参观这个电影院。您为每个人分配一个座位。让 P_i 是分配给人员的座位 i。那么,人 i 到达时间 L_i,交叉座位 1,2,\ldots,P_i-1 坐在座位上 P_i,并按时离开 R_i,交叉座位 1,2,\ldots,P_i-1 退出。
的 不满意 人的 人的 i 是其他人跨座位的次数 P_i 在时间间隔内 L_i 到时间 R_i (不完全包括 L_i 和 R_i).
找到字典顺序最小的排列 P of (1,2,\ldots,N) 最大限度地减少所有人的总体不满 1 to N.
你被给予 T 测试用例,因此找到每个用例的答案。
约束
- 1\le T\le 500
- 1\le N\le 500
- 1\le L_i < R_i\le 2\times N
- L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N 都是不同的。
- 总和 N 所有测试用例最多 500.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N L_1 R_1 L_2 R_2 \vdots L_N R_N
输出
输出 T 行。
的 i- 第行应包含字典顺序最小的排列 P of (1,2,\ldots,N) 最大限度地减少所有人的总体不满 1 to N 为 i- 第一个测试用例,用空格分隔。
示例输入 1
3 3 1 5 2 3 4 6 4 1 5 2 6 3 7 4 8 6 6 10 2 11 7 8 1 9 3 4 5 12
示例输出 1
2 1 3 1 2 3 4 2 4 1 5 3 6
对于第一个测试用例,如果我们设置 P=(2,1,3),过程如下:
- 时间 1:人 1 坐在座位上 2.
- 时间 2:人 2 坐在座位上 1.
- 时间 3:人 2 离开座位 1.
- 时间 4:人 3 坐在座位上 3。人 1的不满情绪增加了 1.
- 时间 5:人 1 离开座位 2.
- 时间 6:人 3 离开座位 3.
此案所有人的不满总和是 1.
不可能使总不满意小于 1,而且, P=(2,1,3) 按字典顺序是最小的 P 完全不满意 1。因此, P=(2,1,3) 就是答案。
对于第二个测试用例,所有人的总不满是 6 对于任何排列 P.