USACO Cow Cars

洛谷 P2909 [USACO08OPEN]牛的车Cow Cars

https://www.luogu.org/problemnew/show/P2909

JDOJ 2584: USACO 2008 Open Silver 3.Cow Cars

https://neooj.com:8082/oldoj/problem.php?id=2584

题目描述

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：复制

输出样例#1：复制

说明

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.

贪心总是和排序联系在一起的？

不信你就看？

大根堆？

优先队列？

排序？

这题不难。

逻辑运算符要注意一下括号的问题。

AC CODE :

#include<cstdio>
#include<algorithm>
using namespace std;
int a[50010];
int n,s,m,d,l,ans;
int main()
{
    scanf("%d%d%d%d",&n,&m,&d,&l);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<=m;i++)
    {
        ans=0;
        for(int j=1;j<=n;j++)
        {
            if(a[j]==0) 
                continue;
            if(a[j]-ans*d>=l || (a[j]-ans*d<0 && l==0))
                ans++,s++,a[j]=0;
        }
    }
    printf("%d",s);
    return 0;
}