[AdditionalFile3117.zip](file://AdditionalFile3117.zip?type=additional_file)

#3117. 「IOI2017」接线

标签: 交互 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

Maryam 是一位电机工程师。她正在为一座通讯塔设计接线方案。在这个塔上有一些分布在不同高度的连接点。一条电线可以用来将任何两个连接点连接起来。每一个连接点都可以都可以接上任意数目的电线。而连接点共有两种：分别为红色连接点及蓝色连接点。

为了表述方便起见，通讯塔会被视为一条直线，而那些红色及蓝色连接点会被视为在这条直线上的一些非负整数坐标。一条电线的长度是该电线所连接的两个连接点的距离。

你要做的是帮 Maryam 找出一个接线的方案，使得满足以下条件：

1. 每个连接点上最少有一条电线连接到一个不同颜色的连接点上。
2. 所用的电线的总长度最短。

输入格式

你需要实现以下的子程序：

int64 min_total_length(int[] r, int[] b)

• $r$：一个长度为 $n$ 的数组，其内以升序排列着所有红色连接点的位置。
• $c$：一个长度为 $m$ 的数组，其内以升序排列着所有蓝色连接点的位置。
• 这个子程序需返回在所有可能的连接方案中，最短电线总长度的那个方案的电线总长度。
• 请注意这个子程序的返回值的类型为 int64。

数据范围与提示

限制条件：

• $1 \leq n, m \leq 100, 000$。
• $0 \leq r_i \leq 10^9$（对于所有 $0 \leq i \leq n - 1$）。
• $0 \leq b_i \leq 10^9$（对于所有 $0 \leq i \leq m - 1$）。
• 数组 $r$ 及数组 $b$ 都已经按升序排好序。
• 在数组 $r$ 以及 $b$ 内的所有 $n + m$ 个值是互不相同的。

子任务：

1. （7分）$n, m \leq 200$。
2. （13分）所有红色连接点的坐标小于任何蓝色连接点的坐标。
3. （10分）在每 $7$ 个连续的连接点内必有至少一个红色连接点以及至少一个蓝色连接点。
4. （25分）所有连接点的坐标范围在 $[1, n + m]$ 内。
5. （45分）没有任何的附加限制。

评分程序样例：

评分程序样例将会读入以下格式的数据：

• 第 $1$ 行：$n\ m$
• 第 $2$ 行：$r_0\ r_1\ \cdots\ r_{n - 1}$
• 第 $3$ 行：$b_0\ b_1\ \cdots\ b_{m - 1}$

评分程序样例将会输出单独一行数据，表示 min_total_length 的返回值。

P3837 [IOI 2017] Wiring

题目背景

这是一道交互题。

本题仅支持 C++ 系列语言，提交时需要包含 wiring.h 头文件，但需要在程序开头包含 vector 头文件以及声明函数 long long min_total_length(std::vector<int> r, std::vector<int> b)。

由于不可名状的 BUG，使用 C++14 (GCC9) 提交会导致 CE，请不要使用其提交。

题目描述

Maryam 是一位电机工程师。她正在为一座通讯塔设计接线方案。在这个塔上有一些分布在不同高度的连接点。一条电线可以用来将任何两个连接点连接起来。每一个连接点都可以接上任意数目的电线。而连接点共有两种：分别为红色连接点及蓝色连接点。

为了表述方便起见，通讯塔会被视为一条直线，而那些红色及蓝色连接点会被视为在这条直线上的一些非负整数坐标。一条电线的长度是该电线所连接的两个连接点间的距离。

你要做的是帮 Maryam 找出一个接线的方案，使得满足以下条件：

1. 每个连接点上最少有一条电线连接到一个不同颜色的连接点上

2. 所用的电线的总长为最短。

实现细节

你需要实现以下的子程序：

long long min_total_length(std::vector<int> r, std::vector<int> b)

• $r$：一个长度为 $n$ 的数组，其内以升序排列着所有红色连接点的位置。

• $b$：一个长度为 $m$ 的数组，其内以升序排列着所有蓝色连接点的位置。

• 这个子程序需返回在所有可能的连接方案中，最短电线总长度的那个方案的电线作为其返回值。

• 请注意这个子程序的返回值的类型为 long long 。

输入格式

你需要实现上面所述的子程序。

输出格式

返回一个 long long 值。

输入输出样例 #1

输入 #1

r = [1, 2, 3, 7]
b = [0, 4, 5, 9, 10]

输出 #1

10

说明/提示

样例中函数传递参数：

min_total_length([1, 2, 3, 7], [0, 4, 5, 9, 10])

以下的图表表述了样例中的数据。

• 图中以水平的方式表示出相关的通讯塔。

• 因题目打印是黑白色的，所以红色接点以较深色来表示，而蓝色接点则以较浅色来表示。

• 图中有 $4$ 个红色的连接点，其位置分别为 $1,2,3$ 及 $7$ 。

• 图中有 $5$ 个蓝色的连接点，其位置分别为 $0,4,5,9$ 及 $10$ 。

• 该例的最优解的电线总长度为 $1+2+2+2+3=10$ ，所以子程序的返回值为 $10$ 。

• 请注意共有两条电线连接在位置为 $7$ 的连接点上。

限制条件

• $1 \leqslant n,m \leqslant 100000$

• $0 \leqslant r[i] \leqslant 10^9$（对于所有$0 \leqslant i \leqslant n-1$）

• $0 \leqslant b[i] \leqslant 10^9$（对于所有$0 \leqslant i \leqslant m-1$）

• 数组$r$及数组$b$都已经按升序排好序。

• 在数组$r$及$b$内的所有$n+m$个值均是不同的。

子任务

1. ($7$ 分) $n,m\leqslant 200$。

2. ($13$ 分) 所有红色接点的位置坐标小于任何蓝色接点的坐标。

3. ($10$ 分) 在每$7$个连续的（接续）的连接点内必有最少一个红色接点及蓝色接点。

4. ($25$ 分) 所有接点在$[1,n+m]$范围内有不同的位置坐标。

5. ($45$ 分) 没有任何附加的限制。