P2909 [USACO08OPEN] Cow Cars S

在 Cowtopia 的高速公路上，有 $N$ 头奶牛（$1 \leq N \leq 50,000$），它们被方便地编号为 $1..N$，分别驾驶着不同的汽车。奶牛 $i$ 可以在 $M$ 条不同的高速车道上行驶（$1 \leq M \leq N$），并且可以以最大速度 $S_i$（$1 \leq S_i \leq 1,000,000$）公里/小时行驶。 在经历了其他糟糕的驾驶体验后，奶牛们讨厌碰撞，并采取了极端措施来避免它们。在这条高速公路上，奶牛 $i$ 会因为在它前面的每一头奶牛而将速度减少 $D$（$0 \leq D \leq 5,000$）公里/小时（但速度不会低于 0 公里/小时）。因此，如果在奶牛 $i$ 前面有 $K$ 头奶牛，那么它将以 $\max[S_i - D \times K, 0]$ 的速度行驶。虽然奶牛实际上可能比直接在它前面的奶牛行驶得更快，但奶牛之间的间距足够大，因此一旦奶牛减速，就不会发生碰撞。 Cowtopia 有一条最低速度法则，要求高速公路上的所有车辆都必须以最低速度 $L$（$1 \leq L \leq 1,000,000$）公里/小时行驶，因此有时一些奶牛在遵循上述规则时将无法上高速公路。编写一个程序，找出在遵守最低速度限制法的情况下，能够在高速公路上行驶的最大奶牛数量。

\* 第 1 行：四个以空格分隔的整数：$N$，$M$，$D$ 和 $L$ \* 第 2 行到第 $N+1$ 行：第 $i+1$ 行用一个整数描述奶牛 $i$ 的初始速度：$S_i$

\* 第 1 行：一个整数，表示可以使用高速公路的最大奶牛数量

有三头奶牛，只有一条车道可供行驶，速度减少为 1，最低速度限制为 5。 可以让两头奶牛上高速公路，方法是先让速度为 5 的奶牛上路，然后让速度为 7 的奶牛上路。 （由 ChatGPT 4o 翻译）