#3117. 「IOI2017」接线

内存限制:256 MiB 时间限制:1000 ms 题目类型:交互
上传者: 匿名

题目描述

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

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

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

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

输入格式

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

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

样例

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

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

QQ截图20190509124135.png

  • 图中以水平的方式表示出相关的通讯塔。
  • 图中有 4 个红色的连接点,其位置分别为 1, 2, 3 7
  • 图中有 5 个蓝色的连接点,其位置分别为 0, 4, 5, 9 10
  • 该例的最优解的电线总长度为 1 + 2 + 2 + 2 + 3 = 10 ,所以子程序的返回值为 10
  • 请注意共有两条电线连接在位置为 7 的连接点上。

在压缩附件包里的文件 examples/01.inexamples/01.out 对应于上述例子。

数据范围与提示

限制条件:

  • 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 的返回值。