Overview

Starting from the origin (coordinate \(0\)) on a number line, you repeatedly deliver up to \(K\) books to \(N\) bookshelves and return to the origin. The problem asks for the minimum total distance traveled to return all books and come back to the origin.

Analysis

The key points to solving this problem are “which books to carry in each trip” and “how to optimize movement”.

1. Consider the positive and negative directions separately Visiting bookshelves at both positive and negative coordinates in a single round trip is inefficient. For example, when delivering books to coordinates \(10\) and \(-10\), making separate round trips costs \(10 \times 2 + 10 \times 2 = 40\). Visiting both at once might look like a movement of \(10 - (-10) = 20\), but since you must return to the origin, the path \(0 \to 10 \to -10 \to 0\) costs \(10 + 20 + 10 = 40\), which is no different from separating them. Moreover, due to the constraint of carrying at most \(K\) books at a time, managing positive and negative directions separately is both simpler and optimal.

2. Prioritize grouping books at farther locations (greedy approach) When going to deliver books to a point \(D\), you can stop at any bookshelves along the way (between the origin and \(D\)) without any additional travel distance. To minimize travel distance, the best strategy is “carry nearby books along when traveling to the farthest location.” Therefore, by sorting coordinates in decreasing order of distance and carrying \(K\) books at a time, we can minimize both the number of round trips and total travel distance.

3. Every trip is a round trip Since the problem explicitly states that “you must return to the counter (origin) at the end,” the travel distance for each group is “the distance to the farthest coordinate in that group \(\times 2\).”

Algorithm

1. Separate the given coordinates into two groups: positive numbers (pos) and negative numbers (neg). Convert negative numbers to their absolute values for easier computation.
2. Sort each group in decreasing order (descending) of distance from the origin.
3. For each group, carry books \(K\) at a time starting from the front (the farthest point).
   • Trip 1: Round trip to the coordinate at index \(0\) (the farthest)
   • Trip 2: Round trip to the coordinate at index \(K\) (the farthest in the next group)
   • Trip 3: Round trip to the coordinate at index \(2K\), and so on…
4. The answer is the sum of all round-trip distances (absolute value of coordinate \(\times 2\)).

Complexity

• Time complexity: \(O(N \log N)\)
  • Partitioning the coordinates takes \(O(N)\), sorting takes \(O(N \log N)\), and summing the distances takes \(O(N/K)\). Overall, sorting is the dominant factor.
• Space complexity: \(O(N)\)
  • Memory is needed for the lists that store the input coordinates.

Implementation Tips

• Efficient input: Since \(N\) can be as large as \(2 \times 10^5\), in Python it is faster to read all input at once using sys.stdin.read().split().

• Using slices: By using range(0, len(list), K), you can easily extract the first element of each group (the maximum distance in that group).

• Handling negative numbers: By converting negative coordinates to their absolute values with abs() beforehand, you can apply exactly the same logic as for positive coordinates.

  Source Code

import sys

# 競技プログラミングの問題「図書館の本の返却」を解くためのプログラムです。
# この問題では、カウンター（座標0）から出発し、最大K冊の本を各書棚（座標Xi）に運び、
# 毎回カウンターに戻るという作業を繰り返します。
# すべての本を運び終えた後、最終的にカウンターに戻るまでの最小移動距離を求めます。

def solve():
    # 標準入力からすべてのデータを一括で読み込み、スペースや改行で分割します。
    # 大規模な入力（N=2*10^5）に対して効率的に処理を行うためです。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 本の冊数, K: 一度に持てる最大冊数
    N = int(input_data[0])
    K = int(input_data[1])
    
    # X: 各書棚の座標
    X = list(map(int, input_data[2:]))
    
    # 正の座標と負の座標に分けます。
    # 座標が0の書棚は存在しない（Xi != 0）という制約があります。
    # 正の側と負の側は独立して（別々の往復で）運ぶのが最適です。
    pos = []
    neg = []
    for x in X:
        if x > 0:
            pos.append(x)
        else:
            # 負の座標は絶対値で管理します。
            neg.append(abs(x))
    
    # それぞれのリストを降順（原点から遠い順）にソートします。
    # 遠い場所にある本を運ぶ際、そのついでに近くの本（最大K-1冊）も運ぶことで、
    # 往復の回数を最小限にし、総移動距離を短縮できます。
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    
    total_distance = 0
    
    # 正の座標側の計算:
    # 遠い順にK冊ずつまとめて運びます。
    # 各グループにおいて、最も遠い座標を往復するため、距離は 2 * pos[i] となります。
    for i in range(0, len(pos), K):
        total_distance += 2 * pos[i]
        
    # 負の座標側の計算:
    # 同様に、遠い順にK冊ずつまとめて往復の距離を加算します。
    for i in range(0, len(neg), K):
        total_distance += 2 * neg[i]
        
    # 求まった最小の総移動距離を出力します。
    # 問題文の指示通り、最後の移動後もカウンターに戻る必要があるため、
    # すべてのグループの移動距離を往復分（2倍）で計算しています。
    print(total_distance)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.