Overview

Choose a contiguous interval \([L,\,R]\) of length \(K\) (\(R=L+K-1\)), and deliver each package on the day within that interval that minimizes its dissatisfaction. Find the minimum total dissatisfaction \(\sum |D_i-x_i|\).

Analysis

1. Once the interval is fixed, the optimal delivery day for each package is uniquely determined

If the operating interval is \([L, R]\), then for a package with desired day \(D_i\): - If \(D_i < L\), deliver on day \(L\) (dissatisfaction \(L-D_i\)) - If \(L \le D_i \le R\), deliver on day \(D_i\) (dissatisfaction \(0\)) - If \(D_i > R\), deliver on day \(R\) (dissatisfaction \(D_i-R\))

In other words, the dissatisfaction is [ \max(0,\,L-D_i) + \max(0,\,D_i-R) ] and the problem reduces to choosing the optimal interval.

2. Why a brute-force approach doesn’t work

Since \(L\) can be up to \(10^9\), trying all possible values of \(L\) is impossible. Moreover, naively computing over all \(N\) packages for each \(L\) would be \(O(N\cdot 10^9)\), which is completely infeasible.

3. We only need to check “breakpoints” (piecewise linear)

The total dissatisfaction [ F(L)=\sum_i \bigl(\max(0,\,L-D_i) + \max(0,\,D_i-(L+K-1))\bigr) ] is a piecewise linear function of \(L\). The shape changes (the slope changes) when crossing the following boundaries:

• The moment some \(D_i\) enters the “\(D_i < L\)” side: around \(L = D_i\)
• The moment some \(D_i\) leaves the “\(D_i > R\)” side: \(D_i = R\), i.e., around \(L = D_i - (K-1)\) (since we deal with integers, \(D_i-K\) and \(D_i-K+1\) are the important values)

Therefore, it suffices to enumerate candidate values of \(L\) near these boundaries (at integer breakpoints) and evaluate them. In the code, the candidates collected are: - \(D_i,\ D_i+1\) - \(D_i-K,\ D_i-K+1\) - And \(1\) due to the constraint \(L\ge 1\)

These are gathered, deduplicated, and then exhaustively checked.

(Example) When \(K=3\), \(R=L+2\). For a package with \(D=10\), the condition for “overflow on the right” is \(10>R\), i.e., \(L\le 7\). The boundary is at \(L=8\) (\(=10-K+1\)), so it suffices to check around \(10-K\) and \(10-K+1\).

Algorithm

1. Sort the desired days array \(D\) in ascending order.
2. Build a prefix sum array pre (pre[t]=D[0]+...+D[t-1]).
3. Enumerate candidate starting days \(L\) as follows, clamping values below \(1\) to \(1\), then sort and deduplicate:
   • \(1\)
   • For each \(d\in D\): \(d,\ d+1,\ d-K,\ d-K+1\)
4. For each candidate \(L\), let \(R=L+K-1\), and use binary search to find:
   • \(i=\#\{D_i < L\}\) (bisect_left)
   • \(j=\#\{D_i \le R\}\) (bisect_right)
5. Compute the total dissatisfaction efficiently:
   • Left side (\(D_i<L\)) contribution: [ \sum_{t< i}(L-D_t)=L\cdot i-\text{pre}[i] ]
   • Right side (\(D_i>R\)) contribution: [ \sum_{t\ge j}(D_t-R)=(\text{pre}[N]-\text{pre}[j]) - R\cdot (N-j) ]
   • Minimize the total left + right.
6. Output the minimum value.

Complexity

• Time complexity: Sorting is \(O(N\log N)\) + \(O(N)\) candidates each with a binary search in \(O(\log N)\), so the overall complexity is \(O(N\log N)\).
• Space complexity: \(O(N)\) for the sorted array, prefix sum array, and candidate array.

Implementation Notes

• By sorting \(D\) and using prefix sums, the contribution of elements outside the interval can be computed collectively in \(O(\log N)\).

• Since \(L\) must be a positive integer, values below \(1\) are clamped to \(1\) during candidate generation.

• There are many duplicate candidates, so sorting followed by a single pass for deduplication is efficient.

• The total can become very large (up to \(N\le 2\times 10^5,\ D_i\le 10^9\)), so 64-bit integers are needed. In Python, int handles this safely.

  Source Code

import sys
from bisect import bisect_left, bisect_right

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    K = next(it)
    D = [next(it) for _ in range(N)]
    D.sort()

    pre = [0] * (N + 1)
    s = 0
    for i, x in enumerate(D, 1):
        s += x
        pre[i] = s
    preN = pre[N]

    cands = [1]
    for d in D:
        a = d
        b = d + 1
        c = d - K
        e = d - K + 1
        if a < 1: a = 1
        if b < 1: b = 1
        if c < 1: c = 1
        if e < 1: e = 1
        cands.append(a)
        cands.append(b)
        cands.append(c)
        cands.append(e)

    cands.sort()
    uniq = []
    prev = None
    for x in cands:
        if x != prev:
            uniq.append(x)
            prev = x

    INF = 10**30
    ans = INF
    km1 = K - 1

    for L in uniq:
        R = L + km1
        i = bisect_left(D, L)
        j = bisect_right(D, R)

        left = L * i - pre[i]
        right = (preN - pre[j]) - R * (N - j)
        total = left + right
        if total < ans:
            ans = total

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.