版权声明:转载请注明出处。 https://blog.csdn.net/u014427196/article/details/40263763

贪心算法 WA了好多 我的心好痛~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define  nMAX 2505
bool vs[nMAX];
struct Cow{
    int min,max;
}cow[nMAX];
struct Lot
{
    int num,cnt;
}lot[nMAX];
int cmp1(const void * a,const void * b)
{
    return (*(Cow*)a).min<(*(Cow*)b).min?1:-1;
}
int cmp2(const void * a,const void * b)
{
    return (*(Lot*)a).num<(*(Lot*)b).num?1:-1;
}
int main()
{
    int i,j,k,nx,ny;
    int ans;
    while(scanf("%d%d",&nx,&ny)!=EOF)
    {
        memset(vs,0,sizeof(vs));
        for(i=0;i<nx;i++)
            scanf("%d%d",&cow[i].min,&cow[i].max);
        for(j=0;j<ny;j++)
            scanf("%d%d",&lot[j].num,&lot[j].cnt);
        qsort(cow,nx,sizeof(cow[0]),cmp1);
        qsort(lot,ny,sizeof(lot[0]),cmp2);
        ans=0;
        for(i=0;i<nx;i++)
            for(j=0;j<ny;j++)
                if(!vs[i]&&lot[j].num>=cow[i].min&&lot[j].num<=cow[i].max&&lot[j].cnt)
                   {
                       lot[j].cnt--;
                       vs[i]=1;
                       ans++;
                   }
            printf("%d\n",ans);

    }
    return 0;
}