103745: [Atcoder]ABC374 F - Shipping
Description
Score : $550$ points
Problem Statement
KEYENCE is famous for quick delivery.
In this problem, the calendar proceeds as Day $1$, Day $2$, Day $3$, $\dots$.
There are orders $1,2,\dots,N$, and it is known that order $i$ will be placed on Day $T_i$.
For these orders, shipping is carried out according to the following rules.
- At most $K$ orders can be shipped together.
- Order $i$ can only be shipped on Day $T_i$ or later.
- Once a shipment is made, the next shipment cannot be made until $X$ days later.
- That is, if a shipment is made on Day $a$, the next shipment can be made on Day $a+X$.
For each day that passes from order placement to shipping, dissatisfaction accumulates by $1$ per day.
That is, if order $i$ is shipped on Day $S_i$, the dissatisfaction accumulated for that order is $(S_i - T_i)$.
Find the minimum possible total dissatisfaction accumulated over all orders when you optimally schedule the shipping dates.
Constraints
- All input values are integers.
- $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}$
Input
The input is given from Standard Input in the following format:
$N$ $K$ $X$ $T_1$ $T_2$ $\dots$ $T_N$
Output
Print the answer as an integer.
Sample Input 1
5 2 3 1 5 6 10 12
Sample Output 1
2
For example, by scheduling shipments as follows, we can achieve a total dissatisfaction of $2$, which is the minimum possible.
- Ship order $1$ on Day $1$.
- This results in dissatisfaction of $(1-1) = 0$, and the next shipment can be made on Day $4$.
- Ship orders $2$ and $3$ on Day $6$.
- This results in dissatisfaction of $(6-5) + (6-6) = 1$, and the next shipment can be made on Day $9$.
- Ship order $4$ on Day $10$.
- This results in dissatisfaction of $(10-10) = 0$, and the next shipment can be made on Day $13$.
- Ship order $5$ on Day $13$.
- This results in dissatisfaction of $(13-12) = 1$, and the next shipment can be made on Day $16$.
Sample Input 2
1 1 1000000000 1000000000000
Sample Output 2
0
Sample Input 3
15 4 5 1 3 3 6 6 6 10 10 10 10 15 15 15 15 15
Sample Output 3
35
Output
得分：550分
问题陈述
KEYENCE 以快速交货而闻名。
在这个问题中，日历按天顺次进行，即第1天，第2天，第3天，……。
有订单1,2,……,N，已知订单i将在第T_i天下单。
对于这些订单，运输按照以下规则进行。
- 最多可以一起运输K个订单。
- 订单i只能在第T_i天或之后发货。
- 一旦发货，下一次发货必须等到X天之后。
- 也就是说，如果在第a天发货，下一次发货可以在第a+X天。
从下单到发货，每过一天，不满情绪累积1。
也就是说，如果订单i在第S_i天发货，该订单累积的不满情绪为(S_i - T_i)。
找出在最优安排发货日期时，所有订单累积的最小可能总不满情绪。
约束条件
- 所有输入值都是整数。
- 1 ≤ K ≤ N ≤ 100
- 1 ≤ X ≤ 10^9
- 1 ≤ T_1 ≤ T_2 ≤ …… ≤ T_N ≤ 10^{12}
输入
输入从标准输入以下格式给出：
N K X T_1 T_2 …… T_N
输出
以整数形式打印答案。
示例输入1
5 2 3 1 5 6 10 12
示例输出1
2
例如，通过以下方式安排发货，我们可以实现总不满情绪为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天。
示例输入2
1 1 1000000000 1000000000000
示例输出2
0
示例输入3
15 4 5 1 3 3 6 6 6 10 10 10 10 15 15 15 15 15
示例输出3
35