← 返回题目列表

AtCoder · awc0046_d

D. 配送中心运营计划

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥是配送中心的经理。配送中心有 N 要投递的包裹,每个包裹都有一个由收件人指定的“首选投递日期”。首选交货日期 i- 第一个包裹是天 D_i.

配送中心可准确运营 K 连续几天。具体来说,高桥选择任意整数 s 并将操作周期设置为 K 天数 s 到今天 s + K - 1 (含)。

高桥必须在此操作期内递送所有包裹。如果交货日期 i-第一个包是 x_i,那么 x_i 必须是满足以下条件的整数 s \leq x_i \leq s + K - 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
  • 第一行包含 N,包裹数量,以及 K,运行期间的天数,以空格分隔。
  • 第二行包含首选交货日期 每个包的 D_1, D_2, \ldots, D_N ,用空格分隔。

输出

在一行中打印所有包裹总不满意的最小值。


示例输入 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