P4916. 最少生产批次

场次：2026年5月9日-开发岗 · 来源：CodeFun2000 P4916

题目描述

工厂需要处理 $n$ 个精密零件，每个零件都有一个参数值。在开始分配之前，你可以对这些零件进行任意重新排序。

你需要将所有零件分配到若干个生产批次中。每个批次至少包含 $1$ 个零件，至多包含 $K$ 个零件。对于一个恰好包含 $t$ 个零件的批次，记该批次中零件参数的最大值为 $M$，最小值为 $m$，则必须满足

$M - m \le D + E \times (t-1)$

每个零件必须且只能属于一个批次。你的目标是使用尽可能少的批次来处理所有零件，请计算最少需要的批次数。

所有测试数据中，$n$ 的总和不超过 $2 \times 10^5$。$D, E$ 的取值范围均为 $0$ 到 $10^9$。$K$ 的取值范围为 $1$ 到 $n$。所有零件的参数均为不超过 $10^9$ 的非负整数。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据组数。 接下来每组测试数据按以下格式给出： 第一行包含四个整数 $n, D, E, K$ ($1 \le n \le 2 \times 10^5$，$0 \le D, E \le 10^9$，$1 \le K \le n$)，含义如上述。 第二行包含 $n$ 个整数，表示每个零件的参数（均为不超过 $10^9$ 的非负整数）。

输出格式

对于每组测试数据，输出一行一个整数，表示最少需要的批次数。

示例

示例 1

输入：

1
5 0 0 2
1 1 2 2 2

输出：

3

说明：

将零件排序后为 [1, 1, 2, 2, 2]。 由于 $D=0, E=0$，条件变为 $M - m \le 0$，即每批内部所有零件参数必须完全相同。每批最多包含 $K=2$ 个零件。 1 有 2 个，正好组成一批；2 有 3 个，最多每批 2 个，因此至少需要两批（例如一批两个 2，另一批一个 2）。总共至少需要 3 批，这也是可以达到的最优方案。

示例 2

输入：

1
4 5 2 3
10 12 15 20

输出：

2

说明：

排序后的序列为 [10, 12, 15, 20]。 由于 $K=3$，所有 4 个零件无法放入同一个批次。 考察一种合法分批：

• 第一批 [10, 12, 15]：包含 $t=3$ 个零件，最大值与最小值之差 $M-m = 15-10 = 5$，条件要求 $5 \le D + E \times (t-1) = 5 + 2 \times 2 = 9$，满足。
• 第二批 [20]：$t=1$，$M-m=0$，自然满足。 因此 2 批即可完成。由于不可能用 1 批完成（零件数超过 $K$），最小批次数为 2。

示例 3

输入：

1
6 2 1 4
3 5 6 10 12 13

输出：

2

说明：

零件排序后为 [3, 5, 6, 10, 12, 13]。 约束为 $D=2, E=1, K=4$。 一种最优方案：

• 第一批 [3, 5, 6]：$t=3$，$M-m=3$，需满足 $3 \le 2 + 1 \times 2 = 4$，合法。
• 第二批 [10, 12, 13]：$t=3$，$M-m=3$，同样合法。 总批次数为 2。 若尝试用更多零件组成一批，例如 [3, 5, 6, 10]，则 $t=4$，$M-m=7$，条件 $7 \le 2 + 1 \times 3 = 5$ 不满足；且无法在一批内放下所有零件（$K=4$ 但极差超限）。因此最少批次为 2。

示例 4

输入：

1
1 10 10 1
100

输出：

1

说明：

只有一个零件，参数为 100。 该零件必须单独构成一个批次，且该批次显然满足任何 $D, E, K$ 约束。最小批次数即为 1。