SP2714 COWCAR - Cow Cars

• 33通过
• 58提交
• 题目来源
• 评测方式 RemoteJudge
• 标签 贪心 队列
• 难度 普及+/提高
• 时空限制 165ms / 1536MB
• 提示：收藏到任务计划后，可在首页查看。

题意翻译

编号为1到N的N只奶牛正各自驾着车打算在牛德比亚的高速公路上飞驰．高速公路有M(1≤M≤N)条车道．奶牛i有一个自己的车速上限Si(l≤Si≤1,000,000)． 在经历过糟糕的驾驶事故之后，奶牛们变得十分小心，避免碰撞的发生．每条车道上，如果某一只奶牛i的前面有南只奶牛驾车行驶，那奶牛i的速度上限就会下降kD个单位，也就是说，她的速度不会超过Si – kD(O≤D≤5000)，当然如果这个数是负的，那她的速度将是0．牛德比亚的高速会路法规定，在高速公路上行驶的车辆时速不得低于/(1≤L≤1,000,000)．那么，请你计算有多少奶牛可以在高速公路上行驶呢？P2909

题目描述

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.

输入输出格式

输入格式：

The first line contains the four integers N, M, D, and L. For the next N lines, line i+1 contains the integer S $_{i}$ .

输出格式：

Print a single integer denoting the maximum number of cows that can take the highway.

输入输出样例

输入样例#1： 复制
3 1 1 5
5
7
5
输出样例#1： 复制
2
提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。