首页 > 代码库 > 贪心/hdu 1051 Wooden Sticks

贪心/hdu 1051 Wooden Sticks

#include<cstdio>#include<algorithm>#include<cstring>using namespace std;struct node{    int l,w;    bool v;};int n;node a[5010];bool cmp(node x,node y){    if (x.l==y.l) return x.w<y.w;    return x.l<y.l;}int main(){    int T;    scanf("%d",&T);    for (int t=1;t<=T;t++)    {        memset(a,0,sizeof(a));        scanf("%d",&n);        for (int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].w);        sort(a+1,a+n+1,cmp);        int ans=0;        for (int i=1;i<=n;i++)            if (a[i].v==0)            {                ans++;                a[i].v=1;                int last=a[i].w;                for (int j=i+1;j<=n;j++)                    if (a[j].w>=last && a[j].v==0)                    {                        a[j].v=1;                        last=a[j].w;                    }            }        printf("%d\n",ans);    }    return 0;}

 

贪心/hdu 1051 Wooden Sticks