洛谷P4767 [IOI 2000] 邮局 加强版 题解

题目链接：P4767 [IOI 2000] 邮局 加强版

题目描述

高速公路旁边有 \(n\) 个村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。两个位置之间的距离是其整数坐标差的绝对值。

现在要建立 \(m\) 个邮局，邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。

你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

输入格式

第一行包含两个整数，分别表示村庄的数量 \(n\) 和邮局的数量 \(m\)。

第二行共 \(n\) 个整数，表示每个村庄的坐标，第 \(i\) 个整数表示第 \(i\) 个村庄的坐标 \(a_i\)。

输出格式

输出一行一个整数表示答案。

数据范围

\(1\le m \le 300, m \le n \le 3000, 1 \le a_i \le 10000\) 。

先写了本题加强版，请参考 洛谷P6246 [IOI2000] 邮局 加强版 加强版 题解 。