/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は図書館の司書として働いています。今日は利用者から返却された N 冊の本を、それぞれ正しい書棚の位置に戻さなければなりません。
図書館は数直線上にあり、カウンターは座標 0 の位置にあります。i 番目の本 (1 \leq i \leq N) を戻すべき書棚は座標 X_i の位置にあります。書棚はカウンターから見て正の方向にも負の方向にも存在する可能性があります。また、異なる本の戻し先が同じ座標であることもあります。
高橋君は最初カウンター（座標 0）にいます。高橋君は一度に最大 K 冊の本を持って運ぶことができます。すべての本を戻すまで、以下の手順を繰り返します。
- カウンター（座標 0）にて、まだ戻していない本の中から 1 冊以上 K 冊以下を好きに選んで持ち出す。
- 数直線上を自由に移動し、持っている本をそれぞれ対応する書棚の座標に到達した時点で降ろす。訪れる書棚の順番は自由に決めてよい。正の方向の書棚と負の方向の書棚を同じ往復の中で訪れてもよい。
- 持ち出した本をすべて正しい書棚に降ろし終えたら、カウンター（座標 0）に戻る。この時点で1回の往復が完了する。
持ち出した本は、その往復中にすべて正しい書棚へ降ろさなければなりません。本をカウンターに持ち帰って次の往復に回すことはできません。最後の往復を含め、毎回必ずカウンターに戻ります。
1回の往復における移動距離は、その往復中に数直線上で実際に移動した距離の合計です。たとえば、座標 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
- 1 行目には、本の冊数を表す整数 N と、一度に持てる本の最大冊数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、i 番目の本を戻すべき書棚の座標を表す整数 X_1, X_2, \ldots, X_N が、スペース区切りで与えられる。
出力
すべての本を戻し終えてカウンターに戻るまでの最小の総移動距離を整数で 1 行に出力せよ。
入力例 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
Score : 400 pts
Problem Statement
Takahashi works as a librarian at a library. Today, he must return N books that were returned by patrons to their correct positions on the shelves.
The library is on a number line, and the counter is located at coordinate 0. The shelf where the i-th book (1 \leq i \leq N) should be placed is at coordinate X_i. Shelves can exist in both the positive and negative directions from the counter. Different books may need to be returned to the same coordinate.
Takahashi starts at the counter (coordinate 0). He can carry at most K books at a time. He repeats the following procedure until all books have been returned:
- At the counter (coordinate 0), choose between 1 and K books (inclusive) from among the books not yet returned, and take them out.
- Move freely along the number line, and drop off each book when reaching the coordinate of its corresponding shelf. The order in which shelves are visited is free to choose. It is allowed to visit shelves in both the positive and negative directions within the same trip.
- After all books taken out have been placed on their correct shelves, return to the counter (coordinate 0). This completes one round trip.
All books taken out must be placed on their correct shelves during that round trip. Books cannot be brought back to the counter to be carried on a later trip. After every round trip, including the last one, Takahashi must return to the counter.
The travel distance of one round trip is the total distance actually traveled along the number line during that trip. For example, if Takahashi moves from coordinate 0 to coordinate 5, then from there to coordinate -3, and then back to coordinate 0, the travel distance is 5 + 8 + 3 = 16.
The sum of travel distances across all round trips is called the total travel distance. Find the minimum total travel distance to return all books to their correct shelves and return to the counter.
Constraints
- 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 (no shelf is at the counter's position)
- All input values are integers
Input
N K X_1 X_2 \ldots X_N
- The first line contains an integer N representing the number of books and an integer K representing the maximum number of books that can be carried at once, separated by a space.
- The second line contains integers X_1, X_2, \ldots, X_N representing the coordinates of the shelves where each book should be returned, separated by spaces.
Output
Print the minimum total travel distance to return all books and come back to the counter, as a single integer on one line.
Sample Input 1
3 2 1 3 5
Sample Output 1
12
Sample Input 2
5 2 -3 -1 2 4 6
Sample Output 2
22
Sample Input 3
8 3 -7 -5 -2 1 3 4 8 10
Sample Output 3
40