Overview

We need to return books to shelves on a number line, with the constraint that we can carry at most \(K\) books at a time, and minimize the total distance traveled before returning to the counter (coordinate \(0\)).

Analysis

Key Insight 1: Mixing left and right (positive and negative) books in one trip doesn’t help

The shelves are on a number line, and the counter is at \(0\).
If we try to visit both “positive positions” and “negative positions” in a single trip, we inevitably have to cross \(0\).

For example, if we carry books to the farthest positive position \(a>0\) and the farthest negative position \(-b<0\) in the same trip, regardless of the order, the travel distance ends up being: - Going \(0 \to a \to -b \to 0\) gives a distance of \(a + (a+b) + b = 2a+2b\)

This is the same as the sum of a round trip to the positive side \(2a\) and a round trip to the negative side \(2b\).
In other words, mixing left and right doesn’t reduce the distance, so we can optimize the positive and negative sides independently.

Key Insight 2: For one side only, “round trip to the farthest point” is optimal

Consider only the positive side (or similarly the negative side). If the shelves for the books carried in one trip are all on the same side, the optimal strategy is:

• Visit shelves in order (either nearest-first or farthest-first) while going to the farthest point, then return.

This is because on a number line, you cannot avoid “going to the farthest point,” and you can drop off books at intermediate shelves along the way.

Therefore, the travel distance for that trip is:
\(2 \times (\text{the farthest distance among books carried in that trip})\)

Why a naive approach doesn’t work

If we try to enumerate all possible assignments of books to trips, or build a complex DP, the number of combinations explodes and is far too slow for \(N \le 2\times 10^5\).

From the observations above, the problem reduces to: - The set of distances on the positive side - The set of distances on the negative side (absolute values)

For each, we simply “group at most \(K\) books per trip, with the cost being the round-trip distance to the farthest book.”

Algorithm

1. For each coordinate \(X_i\):
   • If \(X_i>0\), add it directly to pos
   • If \(X_i<0\), add \(-X_i\) (absolute value) to neg
     (Treat the negative side as “distances” using positive values)
2. Sort pos and neg each in descending order.
3. For each list, it is optimal to group and carry \(K\) books at a time from the front:
   • Since the list is in descending order, the “farthest” in each group is the first element of that group
   • Therefore, look only at elements at indices \(0, K, 2K, \dots\) and add \(2 \times \text{that value}\) to the total
4. The sum of the positive side and negative side totals is the answer.

Concrete example: \(K=3\), positive side distances are [10, 8, 3, 2]:
- 1st trip carries {10, 8, 3}: cost \(2\times 10\) - 2nd trip carries {2}: cost \(2\times 2\)
Total: \(2\cdot 10 + 2\cdot 2\).

Complexity

• Time complexity: \(O(N\log N)\) (dominated by sorting the positive and negative sides)
• Space complexity: \(O(N)\) (storing pos and neg)

Implementation Notes

• By converting negative coordinates using -x, they become “distances” and can be processed with the same logic as the positive side.

• With descending sort, a simple for i in range(0, len(list), K): ans += 2*list[i] picks up “the farthest distance for each trip.”

• Since \(N\) can be large, it is safer to use sys.stdin.readline for input.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    X = list(map(int, input().split()))

    pos = []
    neg = []
    for x in X:
        if x > 0:
            pos.append(x)
        else:
            neg.append(-x)

    pos.sort(reverse=True)
    neg.sort(reverse=True)

    ans = 0
    for i in range(0, len(pos), K):
        ans += 2 * pos[i]
    for i in range(0, len(neg), K):
        ans += 2 * neg[i]

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.