B4179 [厦门小学生 C++ 2024] 战线巡逻

本试题为 2024 年厦门市小学生 C++ 语言**复赛**试题，数据为洛谷自造。 **初赛**为笔试。

在一条战线中，有 $n$ 个需要巡逻的点，为了完成巡逻任务，指挥部计划指派 $k$ 个哨兵，每个哨兵可以自由选择起始位置 $i$，不消耗体力。但哨兵每移动一个单位距离（从 $i$ 到 $i+1$ 或 $i-1$），则消耗 $1$ 点体力。 指挥部的目标是将 $k$ 个哨兵合理部署到战线上，使得： - 所有需要巡逻的点都由至少一名哨兵巡逻过。 - 哨兵总体力消耗的最小。 请你设计一个合理的方案，计算最小的体力消耗，并输出结果。

- 第一行，两个整数，分别是 $k$ 和 $n$； - 第二行，$n$ 个整数，战线中必须巡逻的坐标 $a_i$。

输出消耗的最少体力。

### 样例解释 1 - 哨兵 1 初始点位即为 $-10$，接下来无需移动，消耗为 $0$。 - 哨兵 2 初始点位为 $-1$，接下来需向右移动 $2$ 个位置到点位 $1$，消耗为 $2$。 - 哨兵 3 初始点位即为 $14$，接下来无需移动，消耗为 $0$。 综上，总消耗为 $0+2+0 = 2$。 ### 样例解释 2 - 哨兵 1 初始点位即为 $-100$，接下来无需移动，消耗为 0。 - 哨兵 2 初始点位为 $-11$，接下来无需移动，消耗为 0。 - 哨兵 3 初始点位即为 $-3$，接下来需向右移动 $3$ 个位置至点位 $0$，消耗为 $3$；接下来需向右移动 $1$ 个位置至点位 $2$，消耗为 $1$；接下来需向右移动 $1$ 个位置至点位 $2$，消耗为 $1$；接下来需向右移动 $7$ 个位置至点位 $9$，消耗为 $7$；共计消耗 $3+1+1+7 = 12$。 - 哨兵 4 初始点位即为 $17$，接下来需向右移动 $3$ 个位置，消耗为 $3$。 综上，总消耗为 $0+0+12+3 = 15$。 ### 样例解释 3 根据题意，哨兵巡逻可以做到不消耗体力。 ### 数据范围 对于所有测试数据有：$-10^5 \leq a_i \leq 10^5$，$1 \leq k \leq 10^5$，$1 \leq n \leq 10^5$。 | 测试点 | 特殊性质 A | $k$ | $n$ | |:--------:|:------------:|:---:|:---:| | $1, 2$ | 否 | $k=1$ | $\leq 10^5$ | | $3, 4$ | 是 | $\leq 10^5$ | $\leq 10^5$ | | $5, 6, 7$| 否 | $\leq 10^3$ | $\leq 10^2$ | | $8, 9, 10$ | 否 | $\leq 10^5$ | $\leq 10^5$ | 特殊性质 A：保证 $k \geq n$ 恒成立。