P2909 [USACO08OPEN]牛的车Cow Cars

    • 528通过
    • 1.1K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 排序 贪心 USACO 2008
  • 难度 普及-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    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.

    编号为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).那么,请你计算有多少奶牛可以在高速公路上行驶呢?

    输入输出格式

    输入格式:

    * 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.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。