题解 P2909 【[USACO08OPEN]牛的车Cow Cars】

Sirius_X · 2017-08-16 12:23:31 · 题解

这题只是一道简单的贪心，并不难

题目描述的有点模糊，意思其实就是一头牛跟在K头牛后面，然后判断那头牛的速度-K*D是否>=L，求速度符合L标准的牛的数量

我的思路是：将N头牛读进来，从小到大排好，然后将速度值较小的放在路的前面，尽量让跑得快的，减速减得多一点，就可以符合L了。再把已经上路的牛所在的数组位置，清零，相当于把它拿走了（但要记得拿一个变量记录数量）。最后再做M次循环（因为总共有M条路，一次循环就相当于处理了一条路），输出

以下是我的代码，仅供大家参考。

#include<cstdio>
#include<algorithm>
using namespace std;
int a[50010];
int main(){
    int n,i,j,s=0,m,d,l,ans;
    scanf("%d %d %d %d",&n,&m,&d,&l);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);//排序。
    for(i=1;i<=m;i++){
        ans=0;//每次循环前要清零，这就相当于记录j头牛前面有多少头牛（相当于题目中的K）。
        for(j=1;j<=n;j++){
            if(!a[j]) continue;//如果已经把拿出来了，就无需在判断。
            if(a[j]-ans*d>=l||(a[j]-ans*d<0&&l==0)){//判断。
                ans++;s++;a[j]=0;
            }
        }
    }
    printf("%d\n",s);
    return 0;
}