A 市的交通主干道上,沿直线部署了 N 个环境监测传感器。为了确保数据的准确性,城市管理部门需要派遣一架自动化无人机对其中任意 K 个传感器进行数据采集。
该主干道可以抽象为一条数轴,无人机初始位置位于坐标 0 处。已知第 i 个传感器的坐标为 x_i,且满足 x_1 < x_2 < \dots < x_N。
无人机在数轴上移动的速度为 1 单位长度/秒。当无人机到达传感器所在位置时,可以瞬间完成数据采集。
请你编写程序,计算无人机采集 K 个传感器的数据所需的最短时间。
第一行包含两个由空格隔开的整数 N 和 K,分别表示传感器的总数和需采集数据的传感器数量。
第二行包含 N 个整数 x_1, x_2, \dots, x_N,表示每个传感器的坐标。
输出一个整数,表示完成任务所需的最短时间。
5 3 -30 -10 10 20 50
40
3 2 10 20 30
20
8 5 -9 -7 -4 -3 1 2 3 4
10
传感器坐标为 {-30, -10, 10, 20, 50},需要采集 3 个传感器的数据。
一种可行的最优方案是:
总耗时 10 + 30 = 40 秒。
传感器都在正半轴 {10, 20, 30},采集 2 个。
直接向右移动到 20 位置,中途采集位于 10 位置的传感器的数据,总耗时 20 秒。
对于 100\% 的数据满足 1 \le K \le N \le 10^5,|x_i| \le 10^8,保证 x_i 严格递增。
| 测试点编号 | N | 特殊性质 |
|---|---|---|
| 1 | 1 \le N \le 10 | A |
| 2 | 1 \le N \le 10 | 无 |
| 3 \sim 5 | 1 \le N \le 10^5 | A |
| 6 \sim 10 | 1 \le N \le 10^5 | 无 |
特殊性质 A:所有的 x_i 均满足 x_i \le 0 或 x_i \ge 0,即:所有的 x_i 均为非正数 或 所有的 x_i 均为非负数。