#P5014. [ioi2017]Wiring

    ID: 4113 传统题 1000ms 512MiB 尝试: 71 已通过: 23 难度: 9 上传者: 标签>CF2600省选/NOI-线性 DP前后缀最值一维前缀和交换论证双指针合并有序序列By佚名上传

[ioi2017]Wiring

题目描述

数轴上有 nn 个红色接点和 mm 个蓝色接点,每个接点的坐标各不相同。可以用一根电线连接两个接点,长度等于它们坐标之差的绝对值。同一个接点可以连接多根电线。

请为每个接点至少接上一根通向不同颜色接点的电线,并使所有电线的总长度最小。输出这个最小总长度。

输入格式

第一行两个整数 n,mn,m。

第二行 nn 个严格递增的整数 r0,r1,…,rn−1r_0,r_1,\ldots,r_{n-1},表示红色接点的坐标。

第三行 mm 个严格递增的整数 b0,b1,…,bm−1b_0,b_1,\ldots,b_{m-1},表示蓝色接点的坐标。

输出格式

输出一行一个整数,表示最小总长度。答案可能超出 32 位有符号整数范围。

本站采用标准输入输出。原赛要求实现返回 64 位整数的函数 min_total_length(r,b)。

样例

4 5
1 2 3 7
0 4 5 9 10
10

一种最优方案是连接 (0,1),(2,4),(3,5),(7,9),(7,10)(0,1),(2,4),(3,5),(7,9),(7,10),总长度为 1010。

数据范围

1≤n,m≤1051\le n,m\le 10^5,所有接点的坐标为 [0,109][0,10^9] 内的整数,且 n+mn+m 个坐标两两不同。

原赛子任务 分值 额外限制
1 7 n,m≤200n,m\le 200
2 13 所有红色接点都在所有蓝色接点左边
3 10 按坐标排序后,每 7 个连续接点中至少有一个红点和一个蓝点
4 25 所有坐标在 [1,n+m][1,n+m] 内
5 45 无

原题由 Aleksandar Ilić 为 IOI 2017 编写,题面据原赛材料改写,采用 CC BY 3.0。

原 PDF 题面 · IOI 官方档案