4149 - 采集数据

题目描述

A 市的交通主干道上,沿直线部署了 N 个环境监测传感器。为了确保数据的准确性,城市管理部门需要派遣一架自动化无人机对其中任意 K 个传感器进行数据采集。

该主干道可以抽象为一条数轴,无人机初始位置位于坐标 0 处。已知第 i 个传感器的坐标为 x_i,且满足 x_1 < x_2 < \dots < x_N

无人机在数轴上移动的速度为 1 单位长度/秒。当无人机到达传感器所在位置时,可以瞬间完成数据采集。

请你编写程序,计算无人机采集 K 个传感器的数据所需的最短时间

输入

第一行包含两个由空格隔开的整数 NK,分别表示传感器的总数和需采集数据的传感器数量。

第二行包含 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
说明

样例 1 说明

传感器坐标为 {-30, -10, 10, 20, 50},需要采集 3 个传感器的数据。

一种可行的最优方案是:

  1. 先向左移动到 -10(耗时 10 秒);
  2. 再向右折返移动到 20(经过坐标 0 和 10,在 10 和 20 处采集,耗时 30 秒)。

总耗时 10 + 30 = 40 秒。

样例 2 说明

传感器都在正半轴 {10, 20, 30},采集 2 个。

直接向右移动到 20 位置,中途采集位于 10 位置的传感器的数据,总耗时 20 秒。

数据范围

对于 100\% 的数据满足 1 \le K \le N \le 10^5|x_i| \le 10^8,保证 x_i 严格递增。

测试点编号N特殊性质
11 \le N \le 10A
21 \le N \le 10
3 \sim 51 \le N \le 10^5A
6 \sim 101 \le N \le 10^5

特殊性质 A:所有的 x_i 均满足 x_i \le 0x_i \ge 0,即:所有的 x_i 均为非正数 或 所有的 x_i 均为非负数。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 基础


上一题 下一题