Overview

Given the desired delivery dates for \(N\) packages, the problem asks to minimize the total dissatisfaction when all packages must be delivered within a continuous \(K\)-day operating period.

Analysis

Since we can freely choose the delivery day for each package from within the continuous \(K\)-day period, it is important to select the optimal interval \([s, s+K-1]\). The dissatisfaction when delivering the \(i\)-th package on day \(x\) is \(|D_i - x|\), and the optimal \(x\) within the interval \([s, s+K-1]\) is the value obtained by “clipping” \(D_i\) to that interval, namely \(\max(s, \min(D_i, s+K-1))\).

Therefore, the total dissatisfaction for a given interval \([s, s+K-1]\) can be computed as follows: $\( \sum_{i=1}^{N} \max(s - D_i, 0) + \max(D_i - (s+K-1), 0) \)$

This means a cost of \(s - D_i\) is incurred if \(D_i < s\), a cost of \(D_i - (s+K-1)\) if \(D_i > s+K-1\), and zero cost otherwise.

Simply iterating over all possible values of \(s\) would result in TLE since \(D_i\) can be up to \(10^9\). Instead, we sort \(D\) and observe that the cost function with respect to the left endpoint \(s\) of the interval is a convex function, so we use ternary search to find the minimum.

Furthermore, to efficiently compute the cost for each interval, we use prefix sums to quickly determine the count and sum of elements smaller/larger than \(s\).

Algorithm

1. Read the input and sort the list of desired delivery dates \(D\) in ascending order.
2. Precompute prefix sums.
3. Narrow down the candidates for the left endpoint \(s\) of the interval using ternary search.
4. For each \(s\), determine the corresponding right endpoint \(s+K-1\) and compute the total cost:
   • Obtain the count \(l\_cnt\) and sum \(l\_sum\) of elements where \(D_i < s\) using binary search
   • Similarly obtain the count \(r\_cnt\) and sum \(r\_sum\) of elements where \(D_i > s+K-1\)
   • The cost is: $\( l\_cnt \cdot s - l\_sum + r\_sum - r\_cnt \cdot (s+K-1) \)$
5. After narrowing the search range, compute the exact minimum value in the neighborhood of the candidate \(s\).

Complexity

• Time complexity: \(O(N \log N + T)\) (where \(T\) is the time for ternary search and final candidate evaluation; effectively \(O(N \log N)\))
• Space complexity: \(O(N)\)

Implementation Notes

• \(D\) must be sorted beforehand.

• By using prefix sums, interval sums can be computed efficiently.

• Binary search (bisect) is used to quickly determine the count and sum of elements inside/outside the interval.

• In ternary search, the search range is divided into three parts and narrowed toward the side with lower cost.

• Finally, the cost is actually computed around the neighborhood of the search range to determine the exact minimum value.

  Source Code

import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    D = list(map(int, data[2:]))
    
    D.sort()
    
    # 累積和を計算
    acc = [0] + list(accumulate(D))
    
    min_cost = float('inf')
    
    # 稼働開始日 s を全探索 (最大で D_max - K + 1 まで)
    # しかし N,K,D_i が大きいため、効率的な方法が必要
    
    # 最適な連続区間 [left, left + K - 1] を見つける
    # 各荷物 i の最適な配達日は max(left, min(D[i], left + K - 1)) = median的な考え方ではない
    # 実際には、連続K日の中で、コスト |D[i] - x| の総和を最小にするxの範囲は中央値付近
    
    # よって、連続するK日の区間をスライドさせて、各区間における最小コストを高速に求めたい
    # 区間 [L, R] 内で、各 D[i] をある日 x に寄せたときのコスト総和の最小値を知りたい
    # 最適な x は D のうち区間に含まれる要素の中央値（の一つ）
    
    # スライディングウィンドウ的に、Dの連続部分列の長さKの区間を考えるわけではない
    # あくまで、稼働日が連続K日、荷物はその中に自由に割り当て可能
    
    # 考え方：
    # 稼働日を [s, s+K-1] とする。
    # 各D[i]について、最適な配達日x_i ∈ [s, s+K-1] を選ぶ。
    # 最適なx_iは、max(s, min(D[i], s+K-1)) つまり、D[i]を[s,s+K-1]内にクリップしたもの
    
    # つまり、コストは Σ_i |D[i] - clip(D[i], s, s+K-1)|
    # この関数は凸関数なので、三分探索などで最小値を求められるが、ここでは別のアプローチ
    
    # 別解：Dをソートしておき、連続するK個の要素を区間として選び、それに対応する最適な[s,s+K-1]を決める
    
    # 最も良いのは、Dの中央値近辺をカバーするような区間を選ぶこと
    
    # 方法：
    # Dをソート済みとする。
    # すべての荷物を[s, s+K-1]内で配達するときの最小コストは：
    # Σ_i max(0, |D[i] - clip(D[i], s, s+K-1)|) → 実際にはΣ|min(max(D[i], s), s+K-1) - D[i]|
    
    # 効率的な計算：
    # Dをソートしておく。
    # 稼働区間[s, s+K-1]に対して、Dの中でs未満のものはsに、s+K-1より大きいものはs+K-1に割り当てるのが最適
    # 残りはそのままD[i]に割り当てられる（=不満0）
    
    # よって、Dの中で < s であるものの数をl_cnt, 和をl_sum
    # Dの中で > s+K-1 であるものの数をr_cnt, 和をr_sum
    # とすれば、
    # コスト = l_cnt * s - l_sum + r_sum - r_cnt * (s+K-1)
    
    # これを効率的に計算するために、Dをソートし、sの候補を絞る
    
    # s の候補としては、D[i] または D[i]-K+1 などが候補になる
    
    # だが、もっと良いのは、Dの要素を使って稼働区間を決定すること
    
    # 解法：
    # Dをソートしておく。
    # 稼働区間の左端を L、右端を R = L + K - 1 とする。
    # すべてのD[i]を[L,R]内の日付に移動させる。
    # コストは Σ_i max(L - D[i], 0) + max(D[i] - R, 0)
    
    # つまり、D[i] < L ならコスト L - D[i]
    #       D[i] > R ならコスト D[i] - R
    #       L <= D[i] <= R ならコスト 0
    
    # これを最小化するL,R (R - L + 1 = K) を探す
    
    # Dをソート済みとする
    # Lの候補は D[0] - K + 1 から D[N-1] まで考えられるが、それは無限大
    
    # 実際には、最適なLは D の要素でも、それより前後してもよい？
    # しかし、最適な区間[L,R]は少なくとも1つのD[i]を含むべき
    
    # よって、Lの候補として、D[i] - K + 1 〜 D[i] などを考えても良い
    
    # ここでは、効率的に計算するために、「何番目の荷物までがL未満か」を二分探索で求める
    
    def compute_cost(L):
        R = L + K - 1
        # D[i] < L の個数と和
        from bisect import bisect_left, bisect_right
        idx_L = bisect_left(D, L)
        idx_R_plus1 = bisect_right(D, R)
        
        l_cnt = idx_L
        r_cnt = N - idx_R_plus1
        
        l_sum = acc[l_cnt]
        r_sum = acc[N] - acc[idx_R_plus1]
        
        cost = l_cnt * L - l_sum + r_sum - r_cnt * R
        return cost
    
    # Lの候補を全探索するには多すぎるので、三分探索を行う
    left = min(D) - K
    right = max(D) + 1
    
    for _ in range(100):  # 十分な反復回数
        c1 = left + (right - left) // 3
        c2 = right - (right - left) // 3
        if compute_cost(c1) > compute_cost(c2):
            left = c1
        else:
            right = c2
            
    # 最後に、left周辺のいくつかの整数値で最小値を確認
    res = float('inf')
    for l in range(left - 2, left + 3):
        res = min(res, compute_cost(l))
        
    print(res)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.