分数: 550 点
问题陈述
KEYENCE 以快速交货而闻名。
在此问题中,日历按 Day 进行 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).
当您以最佳方式安排发货日期时,找到所有订单累积的最小可能总不满意率。
约束
- 所有输入值均为整数。
- 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}
输入
输入由标准输入按以下格式给出:
N K X T_1 T_2 \dots T_N
输出
将答案打印为整数。
样本输入 1
5 2 3 1 5 6 10 12
示例输出 1
2
例如,通过如下安排发货,我们可以实现总不满意 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.
示例输入 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