← 返回题目列表

Codeforces · 1650/C

C. 嵌套段系统的权重

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

数轴上有 $$$m$$$ 个点,其中 $$$i$$$ 具有整数坐标 $$$x_i$$$ 和整数权重 $$$w_i$$$。所有点的坐标都不同,点的编号从$$$1$$$到$$$m$$$。

$$$n$$$ 段 $$$[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$$$ 的序列称为嵌套段系统,如果对于每对 $$$i, j$$$ ($$$1 \le i < j \le n$$$) 条件 $$$l_i < l_j < r_j < r_i$$$ 很满意。换句话说,第二个片段严格位于第一个片段内部,第三个片段严格位于第二个片段内部,依此类推。

对于给定的数字$$$n$$$,找到一个嵌套段系统,使得:

- 每段的两端都是 $$$m$$$ 给定点之一;
- 用作线段末端的点的权重 $$$2\cdot n$$$ 之和最小。

例如,令 $$$m = 8$$$。给定的点在图中被标记,它们的权重被标记为红色,它们的坐标被标记为蓝色。创建一个由三个嵌套段组成的系统:

- 第一段的权重:$$$1 + 1 = 2$$$
- 第二段的权重:$$$10 + (-1) = 9$$$
- 第三段的权重:$$$3 + (-2) = 1$$$
- 系统中所有段的权重总和:$$$2 + 9 + 1 = 12$$$

三个嵌套段系统

输入

输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) – 输入测试用例的数量。

每个测试用例之前都会写入一个空行。

每个测试用例的第一行包含两个正整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) 和 $$$m$$$ ($$$2 \cdot n \le m \le 2 \cdot 10^5$$$)。

接下来的 $$$m$$$ 行包含整数对 $$$x_i$$$ ($$$-10^9 \le x_i \le 10^9$$$) 和 $$$w_i$$$ ($$$-10^4 \le w_i \le 10^4$$$) — 点号 $$$i$$$ 的坐标和权重 ($$$1 \le i \le m$$$) 分别。所有 $$$x_i$$$ 都是不同的。

保证所有测试用例的 $$$m$$$ 值之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n + 1$$$ 行:在第一行中,输出组合系统的权重,在接下来的 $$$n$$$ 行中输出恰好两个数字 — 作为第 $$$i$$$ 段端点的点的索引 ($$$1 \le i \le n$$$)。输出线段端点的顺序并不重要——您可以先输出左端点的索引,然后输出右端点的编号,或者反之亦然。

如果有多种方法可以构建具有最小权重的嵌套段系统,请输出其中任何一种。

示例

输入 #1

3

3 8
0 10
-2 1
4 10
11 20
7 -1
9 1
2 3
5 -2

3 6
-1 2
1 3
3 -1
2 4
4 0
8 2

2 5
5 -1
3 -2
1 0
-2 0
-5 -3

输出 #1

12
2 6
5 1
7 8

10
1 6
5 2
3 4

-6
5 1
4 2

注意

第一个测试用例与条件示例一致。可以看出,所组成的系统的重量是最小的。

第二个测试用例只有 $$$6$$$ 点,因此您需要使用它们中的每一个来组成 $$$3$$$ 段。