← 返回题目列表

AtCoder · abc374_f

I. 运输

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

分数: 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