P16851 [GKS 2021 #D] Final Exam

又到了算法与数据结构的期末考试时间！ Edsger 准备了 $N$ 套题目。每套题目包含难度递增的题目序列；第 $i$ 套可以用两个整数 $A_i$ 和 $B_i$（$A_i \le B_i$）描述，表示该套包含难度为 $A_i, A_i+1, \dots, B_i$ 的题目。在所有题目的所有题目中，保证没有两道题目的难度相同。 本学期 Edsger 要测试 $M$ 名学生。他想给每个学生恰好出一道题，题目来自他准备的某套题目中。不能有两名学生做完全相同的题目，因此当 Edsger 用某道题测试一名学生后，这道题就不能再用了。通过无数次讲课、练习和项目，Edsger 估算了第 $j$ 名学生的能力水平为 $S_j$，并希望给该学生出一道难度为 $S_j$ 的题目。不幸的是，这并不总是可行，因为 Edsger 可能没有准备该难度的题目，或者该题目之前已经被其他学生用过了。因此，Edsger 会为第 $j$ 名学生选择一道难度为 $P_j$ 的题目，使得 $|P_j - S_j|$ 最小，并且该难度 $P_j$ 的题目在第 $j$ 名学生之前尚未被任何学生使用过。当存在多个最小差值时，Edsger 总是选择难度较小的题目。注意，为第 $j$ 名学生选择的题目可能会影响之后所有学生的选择，因此你必须按照输入中出现的顺序处理学生。 由于跟踪所有题目可能相当复杂，你能帮助 Edsger 确定他应该给所有学生哪些题目吗？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含两个整数 $N$ 和 $M$：分别是题目的套数和学生的数量。接下来 $N$ 行描述每套题目。 这些行中的每一行包含两个整数 $A_i$ 和 $B_i$，表示第 $i$ 套题目中最容易和最难的题目难度。最后，测试用例以一行结束，该行包含 $M$ 个整数 $S_1, S_2, \dots, S_M$，表示学生按测试顺序的能力水平。

对于每个测试用例，输出一行，格式为 `Case #x: P1 P2 ... PM`，其中 $x$ 是测试用例编号（从 $1$ 开始），$P_j$ 是给第 $j$ 名学生的题目难度。

在样例 #1 中，有 $N = 5$ 套题目和 $M = 4$ 名学生。 - 对于第一名学生，我们寻找难度最接近其能力水平 $S_1 = 14$ 的题目。最小差值的题目是难度 $12$，可以在第三套题目中找到，因此 $P_1 = 12$。 - 对于第二名学生，我们寻找难度最接近其能力水平 $S_2 = 24$ 的题目。幸运的是，我们可以在第四套题目中找到恰好为 $24$ 的题目，因此 $P_2 = 24$。 - 对于第三名学生，我们再次寻找难度最接近其能力水平 $S_3 = 24$ 的题目。由于难度 $24$ 已经被使用，不能再用。最接近的题目难度是 $11$，因为 $12$ 也被用过了。因此 $P_3 = 11$。 - 最后，对于第四名学生，我们寻找难度最接近其能力水平 $S_4 = 4$ 的题目。有两个题目的差值相同：$2$ 和 $6$。我们选择难度较小的题目，所以 $P_4 = 2$。 在样例 #2 中，有 $N = 1$ 套题目和 $M = 1$ 名学生。唯一的一套题目中只有一道题，因此我们只能用这道题来测试这唯一的学生，所以 $P_1 = 42$。 ### 限制条件 $1 \le T \le 100$。 在所有题目中，没有两道题目的难度相同。 题目总数大于等于学生人数。 **测试集 1** $1 \le N \le 1000$。 $1 \le M \le 1000$。 对于所有 $i$，$1 \le A_i \le B_i \le 1000$。 对于所有 $j$，$1 \le S_j \le 1000$。 **测试集 2** $1 \le N \le 10^5$。 $1 \le M \le 10^5$。 对于所有 $i$，$1 \le A_i \le B_i \le 10^{18}$。 对于所有 $j$，$1 \le S_j \le 10^{18}$。 翻译由 DeepSeek V4 Pro 完成