Overview

Given \(N\) desired delivery dates \(D_i\), the problem asks to choose an interval \([s, s+K-1]\) of length \(K\) to minimize the total distance from each \(D_i\) to the interval (0 if \(D_i\) is within the interval).

Analysis

1. Understanding the Dissatisfaction

When a package has desired date \(D_i\) and the operating period is \([s, e]\) (where \(e = s + K - 1\)), to minimize that package’s dissatisfaction, we should deliver it on the day within the period closest to \(D_i\). - When \(D_i < s\): Delivering on day \(s\) is optimal, with dissatisfaction \(s - D_i\) - When \(s \le D_i \le e\): We can deliver on day \(D_i\), with dissatisfaction \(0\) - When \(D_i > e\): Delivering on day \(e\) is optimal, with dissatisfaction \(D_i - e\)

Combining these, the dissatisfaction per package can be written as \(\max(0, s - D_i, D_i - e)\).

2. Properties of the Function and the “Median” Approach

Let \(f(s)\) be the total dissatisfaction across all packages. This function is convex (a convex-downward graph) with respect to \(s\). Consider how the slope of \(f(s)\) changes. When \(s\) increases by \(1\): - Dissatisfaction increases by \(1\) for packages where \(D_i < s\) - Dissatisfaction decreases by \(1\) for packages where \(D_i > s + K - 1\) - Dissatisfaction does not change for other packages

Therefore, the slope of \(f(s)\) is (number of packages with \(D_i < s\)) - (number of packages with \(D_i > s + K - 1\)). The location where this slope becomes \(0\) is the candidate for the minimum.

Reorganizing the conditions: - \(D_i < s\) \(\iff\) \(s > D_i\) - \(D_i > s + K - 1\) \(\iff\) \(s < D_i - K + 1\)

This suggests that the slope becomes \(0\) near the median of the \(2N\) values (\(D_i\) and \(D_i - K + 1\)). Specifically, if we sort these \(2N\) values in ascending order as \(P_1, P_2, \ldots, P_{2N}\), then \(f(s)\) is minimized for \(s\) in the range \([P_N, P_{N+1}]\).

3. Handling the Constraint \(s \ge 1\)

Since the problem requires \(s\) to be a positive integer, if the computed median range falls below \(1\), we set \(s=1\). That is, \(s = \max(1, P_N)\) minimizes \(f(s)\) while satisfying the constraint.

Algorithm

1. Sort the given \(D_i\).
2. Put all \(2N\) points \(\{D_i\} \cup \{D_i - K + 1\}\) into a list \(P\) and sort it.
3. Set \(s = \max(1, P_N)\) (or \(P[N-1]\) in 0-indexed) as the optimal starting day.
4. Compute the ending day \(e = s + K - 1\).
5. For each package, compute the following total (can be sped up using prefix sums or binary search):
   • If \(D_i < s\): \((s - D_i)\)
   • If \(D_i > e\): \((D_i - e)\)
   • Otherwise: \(0\)

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting \(D_i\) takes \(O(N \log N)\).
  • Sorting \(P\) with \(2N\) elements takes \(O(N \log N)\).
  • Computing dissatisfaction using prefix sums and binary search (or scanning) takes \(O(N)\) or \(O(\log N)\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the arrays \(D, P\) and prefix sum arrays.

Implementation Notes

• Efficient Computation: Since \(N=2 \times 10^5\) can be large, when computing the total dissatisfaction, instead of iterating through all elements each time, use prefix sums to obtain range sums in \(O(1)\).

• Median Selection: Any value between the \(N\)-th and \((N+1)\)-th elements of the sorted \(2N\) data points gives the minimum. In the code, \(P[N-1]\) is used.

• Size of \(K\) and \(D_i\): Since \(K\) and \(D_i\) can be up to \(10^9\), the answer may not fit in a 32-bit integer. In Python, this is handled automatically with arbitrary-precision integers, but in other languages, long long or equivalent types must be used.

  Source Code

import sys
from bisect import bisect_left, bisect_right

def solve():
    # 高速な入力を実現するためにsys.stdin.read().split()を使用
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 荷物の個数, K: 稼働期間の日数
    N = int(input_data[0])
    K = int(input_data[1])
    # D: 各荷物の希望配達日
    D = [int(x) for x in input_data[2:]]
    # 希望配達日を昇順にソート
    D.sort()
    
    # 稼働期間を [s, s + K - 1] としたとき、
    # 各荷物に対する最小不満度は max(0, s - Di, Di - (s + K - 1)) となる。
    # この不満度の合計を最小化する問題は、s に関する凸関数の最小値を求める問題であり、
    # その最小値は 2N 個の点 {Di} と {Di - K + 1} の中央値の範囲内で達成される。
    
    # 特徴点（不満度関数の傾きが変化する点）をすべてリストに加える
    P = D + [x - K + 1 for x in D]
    P.sort()
    
    # 2N 個の点の中央値の範囲は [P[N-1], P[N]] となる。
    # s は任意の正整数（s >= 1）である必要があるため、最適な s を以下のように選ぶ。
    # 中央値の範囲が 1 以上の整数を含むならそのいずれかを、
    # 範囲がすべて 1 未満なら s = 1 を選ぶことで、s >= 1 の範囲での最小値が得られる。
    s = max(1, P[N - 1])
    e = s + K - 1
    
    # 不満度の合計 f(s) を計算する。
    # f(s) = sum_{Di < s} (s - Di) + sum_{Di > s + K - 1} (Di - (s + K - 1))
    
    # 計算を高速化するために累積和を準備
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i + 1] = prefix_sum[i] + D[i]
        
    # Di < s となる荷物の個数と合計
    idx_low = bisect_left(D, s)
    count_low = idx_low
    sum_low = prefix_sum[idx_low]
    cost_low = count_low * s - sum_low
    
    # Di > e となる荷物の個数と合計
    idx_high = bisect_right(D, e)
    count_high = N - idx_high
    sum_high = prefix_sum[N] - prefix_sum[idx_high]
    cost_high = sum_high - count_high * e
    
    # 最小の不満度合計を出力
    print(cost_low + cost_high)

if __name__ == '__main__':
    solve()

---

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