← 返回题目列表

AtCoder · arc200_c

C. 电影院

中文机器翻译题面 查看原题

分数: 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.