← 返回题目列表

Codeforces · 427/E

E. 警察巡逻

中文机器翻译题面 查看原题

想象一下,您的城市是一个具有笛卡尔坐标系的无限二维平面。您所在城市唯一受犯罪影响的道路是 x 轴。目前,沿路有n名犯罪分子。这条路上还没有建警察局,所以市长想建一个。

由于你将负责这个新的警察局,市长要求你选择一个合适的位置(某个整数点)来建造它。你应该选择警察局的最佳位置,这样你就可以最大限度地减少抓捕犯罪任务的总时间。你抓捕罪犯的任务只能在这个车站进行。

新车站将只有一辆巡逻车。你将乘这辆车去见罪犯,把他们抬上车,带回警察局,关进监狱。巡逻车一次最多可运载 m 名罪犯。请注意,犯罪分子并不知道您的任务。所以,他们不会逃跑,而是留在原地。

你的任务是找到警察局的位置,这样你抓捕所有罪犯所需的总距离就会尽可能小。请注意,您还可以在一名或多名罪犯已经存在的位置上建立警察局。在这种情况下,所有这些罪犯都会立即被捕。

输入

输入的第一行将包含两个由空格分隔的整数 n (1 ≤ n ≤ 106) 和 m (1 ≤ m ≤ 106)。下一行将包含 n 个由空格分隔的整数。第 i 个整数是第 i 个罪犯在 x 轴上的位置。位置的绝对值不会超过109。如果犯罪分子的位置为x,则他/她位于平面的点(x,0)。

罪犯的职位将以非降序排列。请注意,飞机的某个位置可能有不止一名犯罪分子。

注意:由于输入/输出的大小可能非常大,因此请勿在您的语言中使用慢速输入/输出技术。例如,不要在 C++ 中使用输入/输出流(cin、cout)。

输出

打印一个整数,这意味着抓获所有罪犯所需的最小可能距离。

示例

输入 #1

3 6
1 2 3

输出 #1

4

输入 #2

5 5
-7 -6 -3 -1 1

输出 #2

16

输入 #3

1 369
0

输出 #3

0

输入#4

11 2
-375 -108 1336 1453 1598 1892 2804 3732 4291 4588 4822

输出#4

18716