分数: 400 点
问题陈述
有 N 房屋编号为 数轴上的 1 to N 。 房子 i 位于坐标 X_i。多个房屋可能位于同一坐标。
你放置 M 数轴上任意实际坐标处的基站。然后,您设置一个非负整数 信号强度 每个基站的 。
当基站的信号强度设置为 x,来自该基站的信号到达房屋当且仅当基站和房屋之间的距离最多为 \displaystyle\frac{x}{2}。 特别是,当 x=0,信号仅到达与基站位于同一坐标的房屋。
当基站的位置和信号强度设置为至少一个基站的信号到达每所房屋时,求信号强度的最小可能总和。
可以证明,对于任何满足约束的输入,答案都是整数。
约束
- 1 \leq M \leq N \leq 5 \times 10^5
- 1 \leq X_i \leq 10^{12} (1 \leq i \leq N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M X_1 \dots X_N
输出
将答案作为整数输出在一行中。
示例输入 1
7 3 5 10 15 20 8 14 15
示例输出 1
6
通过如下放置三个基站,信号可以到达所有房屋。
- 放置具有信号强度的基站 5 位于坐标处 7.5。这个基站到达千家万户 1,2,5.
- 放置具有信号强度的基站 1 位于坐标处 14.5。这个基站到达千家万户 3,6,7.
- 放置具有信号强度的基站 0 位于坐标处 20。这个基站到达家 4.
这种情况下的信号强度总和是 6.
信号强度总和小于的布置不可能满足条件 6,所以输出 6.
示例输入 2
7 7 5 10 15 20 8 14 15
示例输出 2
0
示例输入 3
7 1 5 10 15 20 8 14 15
示例输出 3
15