Shipping

题目描述

KEYENCE 因快速交付而闻名。

在本问题中，日历从第 $1$ 天、第 $2$ 天、第 $3$ 天、$\dots$ 依次进行。有订单 $1,2,\dots,N$，已知订单 $i$ 会在第 $T_i$ 天被下达。
对于这些订单，发货按以下规则进行。

最多可将 $K$ 个订单一起发货。订单 $i$ 只能在第 $T_i$ 天或之后发货。一旦进行一次发货，直到 $X$ 天之后才能进行下一次发货。也就是说，如果在第 $a$ 天发货，则下一次发货可以在第 $a+X$ 天进行。

对于每个从下单到发货经过的天数，不满意味着每天增加 $1$ 的不满值。
也就是说，如果订单 $i$ 在第 $S_i$ 天发货，则该订单累积的不满为 $(S_i - T_i)$ 。当你优化安排发货日期时，求所有订单累积的不满总和的最小可能值。

输入按以下格式从标准输入给出： $N$ $K$ $X$ $T_1$ $T_2$ $\dots$ $T_N$

输出答案，格式为整数。

5 2 3
1 5 6 10 12

1 1 1000000000
1000000000000

15 4 5
1 3 3 6 6 6 10 10 10 10 15 15 15 15 15

所有输入值均为整数。 $1 \le K \le N \le 100$ $1 \le X \le 10^9$ $1 \le T_1 \le T_2 \le \dots \le T_N \le 10^{12}$ 例如，通过如下安排发货，我们可以得到总不满为 $2$ ，这是可能的最小值。

在第 $1$ 天发货订单 $1$ 。这产生不满 $(1-1) = 0$ ，且下一次发货可以在第 $4$ 天进行。

在第 $6$ 天发货订单 $2$ 和 $3$ 。这产生不满 $(6-5) + (6-6) = 1$ ，且下一次发货可以在第 $9$ 天进行。

在第 $10$ 天发货订单 $4$ 。这产生不满 $(10-10) = 0$ ，且下一次发货可以在第 $13$ 天进行。

在第 $13$ 天发货订单 $5$ 。这产生不满 $(13-12) = 1$ ，且下一次发货可以在第 $16$ 天进行。

标签: AtCoder|abc374F

AtCoder|abc374F