AT_abc374_f [ABC374F] Shipping

题目描述

Keyence 以即日发货闻名。

在本题中，日历按照 $1$ 日、$2$ 日、$3$ 日、$\dots$ 这样依次递增。

共有 $1,2,\dots,N$ 个订单，第 $i$ 个订单在第 $T_i$ 天产生。
对于这些订单，需要按照以下规则进行发货：

• 每次发货最多可以同时处理 $K$ 个订单。
• 第 $i$ 个订单只能在 $T_i$ 日及之后发货。
• 每次发货后，必须等待 $X$ 天后才能进行下一次发货。
  • 也就是说，如果在第 $a$ 天进行了发货，则下一次发货最早可以在第 $a+X$ 天进行。

每个订单从下单到发货，每延迟 $1$ 天会累计 $1$ 点不满度。
也就是说，如果第 $i$ 个订单在第 $S_i$ 天发货，则该订单累计的不满度为 $(S_i - T_i)$。

请合理安排发货的时机，使所有订单累计的不满度总和达到最小，并输出该最小值。

输入格式

输入以如下格式从标准输入读入。

$N$ $K$ $X$ $T_1$ $T_2$ $\dots$ $T_N$

输出格式

请输出一个整数，表示最小可能的不满度总和。

输入输出样例 #1

输入 #1

5 2 3
1 5 6 10 12

输出 #1

2

输入输出样例 #2

输入 #2

1 1 1000000000
1000000000000

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

35

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq K \leq N \leq 100$
• $1 \leq X \leq 10^9$
• $1 \leq T_1 \leq T_2 \leq \dots \leq T_N \leq 10^{12}$

样例解释 1

例如，按照如下方式发货，可以使不满度总和为 $2$，这是可以达到的最小值。

• 第 $1$ 个订单在第 $1$ 天发货。
• 这样该订单的不满度为 $(1-1)=0$，下次发货最早在第 $4$ 天。
• 第 $2$、$3$ 个订单在第 $6$ 天发货。
• 这样这两个订单的不满度为 $(6-5)+(6-6)=1$，下次发货最早在第 $9$ 天。
• 第 $4$ 个订单在第 $10$ 天发货。
• 这样该订单的不满度为 $(10-10)=0$，下次发货最早在第 $13$ 天。
• 第 $5$ 个订单在第 $13$ 天发货。
• 这样该订单的不满度为 $(13-12)=1$，下次发货最早在第 $16$ 天。

由 ChatGPT 4.1 翻译