/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は配送センターの管理者です。配送センターでは N 個の荷物を届ける予定があり、それぞれの荷物には届け先が指定した「希望配達日」があります。i 番目の荷物の希望配達日は D_i 日目です。
配送センターはちょうど連続する K 日間だけ稼働させることができます。具体的には、任意の整数 s を選び、s 日目から s + K - 1 日目までの K 日間（両端を含む）を稼働期間とします。
高橋君は、すべての荷物をこの稼働期間内に配達しなければなりません。i 番目の荷物の配達日を x_i とすると、x_i は s \leq x_i \leq s + K - 1 を満たす整数でなければなりません。1 日に配達できる荷物の個数に上限はなく、同じ日に複数の荷物を配達することもできます。
i 番目の荷物を x_i 日目に配達した場合、その荷物の不満度は |D_i - x_i| です。希望配達日ちょうどに届ければ不満度は 0 ですが、希望日から離れるほど不満度は大きくなります。
高橋君は稼働期間の開始日 s を適切に選び、さらに各荷物の配達日を稼働期間内で適切に決めることで、すべての荷物の不満度の合計 \displaystyle \sum_{i=1}^{N} |D_i - x_i| を最小化したいと考えています。その最小値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \leq D_i \leq 10^9
- 入力はすべて整数
入力
N K D_1 D_2 \ldots D_N
- 1 行目には、荷物の個数を表す N と、稼働期間の日数を表す K が、スペース区切りで与えられる。
- 2 行目には、各荷物の希望配達日を表す D_1, D_2, \ldots, D_N が、スペース区切りで与えられる。
出力
すべての荷物の不満度の合計の最小値を 1 行で出力せよ。
入力例 1
5 3 1 2 3 4 5
出力例 1
2
入力例 2
4 10 5 8 12 20
出力例 2
6
入力例 3
7 5 100 102 105 110 115 118 120
出力例 3
34
Score : 400 pts
Problem Statement
Takahashi is the manager of a delivery center. The delivery center has N packages to deliver, and each package has a "preferred delivery date" specified by its recipient. The preferred delivery date of the i-th package is day D_i.
The delivery center can operate for exactly K consecutive days. Specifically, Takahashi chooses any integer s and sets the operation period to be the K days from day s to day s + K - 1 (inclusive).
Takahashi must deliver all packages within this operation period. If the delivery date of the i-th package is x_i, then x_i must be an integer satisfying s \leq x_i \leq s + K - 1. There is no upper limit on the number of packages that can be delivered in a single day, and multiple packages can be delivered on the same day.
If the i-th package is delivered on day x_i, the dissatisfaction for that package is |D_i - x_i|. If the package is delivered exactly on the preferred delivery date, the dissatisfaction is 0, but the further the delivery date is from the preferred date, the greater the dissatisfaction.
Takahashi wants to choose the starting day s of the operation period appropriately, and also decide the delivery date of each package within the operation period appropriately, in order to minimize the total dissatisfaction of all packages \displaystyle \sum_{i=1}^{N} |D_i - x_i|. Find this minimum value.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \leq D_i \leq 10^9
- All inputs are integers
Input
N K D_1 D_2 \ldots D_N
- The first line contains N, the number of packages, and K, the number of days in the operation period, separated by a space.
- The second line contains the preferred delivery dates D_1, D_2, \ldots, D_N of each package, separated by spaces.
Output
Print the minimum value of the total dissatisfaction of all packages in one line.
Sample Input 1
5 3 1 2 3 4 5
Sample Output 1
2
Sample Input 2
4 10 5 8 12 20
Sample Output 2
6
Sample Input 3
7 5 100 102 105 110 115 118 120
Sample Output 3
34