#P5014. [ioi2017]Wiring
[ioi2017]Wiring
题目描述
数轴上有 个红色接点和 个蓝色接点,每个接点的坐标各不相同。可以用一根电线连接两个接点,长度等于它们坐标之差的绝对值。同一个接点可以连接多根电线。
请为每个接点至少接上一根通向不同颜色接点的电线,并使所有电线的总长度最小。输出这个最小总长度。
输入格式
第一行两个整数 。
第二行 个严格递增的整数 ,表示红色接点的坐标。
第三行 个严格递增的整数 ,表示蓝色接点的坐标。
输出格式
输出一行一个整数,表示最小总长度。答案可能超出 32 位有符号整数范围。
本站采用标准输入输出。原赛要求实现返回 64 位整数的函数 min_total_length(r,b)。
样例
4 5
1 2 3 7
0 4 5 9 10
10
一种最优方案是连接 ,总长度为 。
数据范围
,所有接点的坐标为 内的整数,且 个坐标两两不同。
| 原赛子任务 | 分值 | 额外限制 |
|---|---|---|
| 1 | 7 | |
| 2 | 13 | 所有红色接点都在所有蓝色接点左边 |
| 3 | 10 | 按坐标排序后,每 7 个连续接点中至少有一个红点和一个蓝点 |
| 4 | 25 | 所有坐标在 内 |
| 5 | 45 | 无 |
原题由 Aleksandar Ilić 为 IOI 2017 编写,题面据原赛材料改写,采用 CC BY 3.0。