[USACO08OPEN] Cow Cars S
题意翻译
有 $N$ 头奶牛 $(1 \le N \le 50000)$,编号 $1 \sim N$。它们正各自驾着车打算在高速公路上飞驰.高速公路有 $M(1\leq M\leq N)$ 条车道。奶牛 $i$ 有一个自己的车速上限 $S_i \ (1\leq S_i\leq 10^6)$。
在经历过糟糕的驾驶事故之后,奶牛们变得十分小心,避免碰撞的发生。每条车道上,如果某一只奶牛 $i$ 的前面有 $k$ 只奶牛驾车行驶,那奶牛 $i$ 的速度上限就会下降 $k\times D$ 个单位,也就是说,她的速度不会超过 $S_i - k \times D(0\leq D\leq 5000)$,当然如果这个数是负的,那她的速度将是 $0$。高速公路法规定,在高速公路上行驶的车辆时速不得低于 $L \ (1 \le L \le 10 ^ 6)$。
求:最多有多少奶牛可以在高速公路上行驶。
题目描述
N (1 <= N <= 50,000) cows conveniently numbered 1..N are driving in separate cars along a highway in Cowtopia. Cow i can drive in any of M different high lanes (1 <= M <= N) and can travel at a maximum speed of S\_i (1 <= S\_i <= 1,000,000) km/hour.
After their other bad driving experience, the cows hate collisions and take extraordinary measures to avoid them. On this highway, cow i reduces its speed by D (0 <= D <= 5,000) km/hour for each cow in front of it on the highway (though never below 0 km/hour). Thus, if there are K cows in front of cow i, the cow will travel at a speed of max[S\_i - D \* K, 0]. While a cow might actually travel faster than a cow directly in front of it, the cows are spaced far enough apart so crashes will not occur once cows slow down as
described,
Cowtopia has a minimum speed law which requires everyone on the highway to travel at a a minimum speed of L (1 <= L <= 1,000,000) km/hour so sometimes some of the cows will be unable to take the highway if they follow the rules above. Write a program that will find the maximum number of cows that can drive on the highway while obeying the minimum speed limit law.
输入输出格式
输入格式
\* Line 1: Four space-separated integers: N, M, D, and L
\* Lines 2..N+1: Line i+1 describes cow i's initial speed with a single integer: S\_i
输出格式
\* Line 1: A single integer representing the maximum number of cows that can use the highway
输入输出样例
输入样例 #1
3 1 1 5
5
7
5
输出样例 #1
2
说明
There are three cows with one lane to drive on, a speed decrease of 1, and a minimum speed limit of 5.
Two cows are possible, by putting either cow with speed 5 first and the cow with speed 7 second.