← 返回题目列表

AtCoder · awc0087_d

D. 归还图书馆书籍

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

分数: 400 分

问题陈述

高桥在一家图书馆担任图书管理员。今天他必须回来 N 顾客归还到书架上正确位置的书籍。

图书馆位于数轴上,计数器位于坐标 0。架子所在的地方 i第本书 (1 \leq i \leq N) 应放置在坐标处 X_i。货架可以存在于柜台的正向和负向。不同的书籍可能需要返回到同一坐标。

高桥从柜台开始(坐标 0)。他最多能带 K 一次书籍。他重复以下过程,直到归还所有书籍:

  1. 在柜台处(坐标 0),选择 尚未归还的图书中的 1 和 K 图书(含),取出。
  2. 沿着数轴自由移动,到达对应书架的坐标后将每本书放下。访问货架的顺序可以自由选择。同一行程内允许正反两个方向访问货架。
  3. 所有取出的书都放在正确的书架上后,返回柜台(坐标 0)。这样就完成了一次往返。

在此往返期间,所有取出的书籍都必须放置在正确的书架上。书籍不能带回柜台以便在以后的旅行中携带。每次往返后,包括最后一次,高桥都必须返回柜台。

一次往返的行驶距离是该行程中沿数轴实际行驶的总距离。例如,如果高桥从坐标移动 0 协调 5,然后从那里坐标 -3,然后回到坐标 0,行驶距离为 5 + 8 + 3 = 16.

所有往返行程的行驶距离之和称为 总行驶距离。求出将所有书籍放回正确书架并返回柜台的最小总行程距离。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • -10^9 \leq X_i \leq 10^9
  • X_i \neq 0 (柜台位置无货架)
  • 所有输入值均为整数

输入

N K
X_1 X_2 \ldots X_N
  • 第一行包含一个整数 N 代表书籍数量和一个整数 K 代表一次可以携带的最大书籍数量,以空格分隔。
  • 第二行包含整数 X_1, X_2, \ldots, X_N 表示每本书应归还的书架坐标,以空格分隔。

输出

打印归还所有书籍并返回柜台的最小总行进距离,作为一行上的单个整数。


示例输入 1

3 2
1 3 5

示例输出 1

12

示例输入 2

5 2
-3 -1 2 4 6

示例输出 2

22

示例输入 3

8 3
-7 -5 -2 1 3 4 8 10

示例输出 3

40