#P1980. Pku3375 Network Connection

    ID: 1003 传统题 1000ms 162MiB 尝试: 209 已通过: 49 难度: 7 上传者: 标签>CF2300提高+/省选-交换论证有限候选集缩减线性 DP前后缀最值滚动数组计数排序同向双指针

Pku3375 Network Connection

题目描述

数轴上有 mm 个网络接口和 nn 台计算机。接口坐标为 B1,…,BmB_1,\dots,B_m,计算机坐标为 A1,…,AnA_1,\dots,A_n。每台计算机必须连到一个网络接口,每个接口最多连接一台计算机。不同设备可以有相同坐标,仍按各自的编号区分。

把计算机 ii 连到接口 jj 的代价为 ∣Ai−Bj∣|A_i-B_j|。求所有计算机都接入网络所需的最小总代价。

输入格式

第一行两个整数 m,nm,n,满足 1≤n≤20001\le n\le2000、n≤m≤106n\le m\le10^6。

接下来 mm 行,每行一个网络接口的坐标。然后 nn 行,每行一台计算机的坐标。本站评测中的坐标都是 [0,106][0,10^6] 内的整数。

输出格式

输出一个整数,表示最小总代价。

4 2
1
10
12
20
11
15
4

题目来源