学步园

        先排序，然后贪心选..........虽然不会证为什么贪心可以.......

#include <stdio.h>
#include <stdlib.h>

typedef struct tStick{
	int l;
	int w;
}Stick;
int n;
Stick s[5000];
int used[5000];

int cmp(const void* x1,const void* y1){
	Stick* x=(Stick*)x1;
	Stick* y=(Stick*)y1;
	int t=x->l-y->l;
	return t==0?x->w-y->w:t;
}

int main(void){
	int T,i,j,l,w,re;
	scanf("%d",&T);
	while(T--){
		re=0;
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d %d",&l,&w);
			s[i].l=l;
			s[i].w=w;
			used[i]=0;
		}
		qsort(s,n,sizeof(Stick),cmp);
		for(i=0;i<n;i++){
			if(used[i]){
				continue;
			}
			l=s[i].l;
			w=s[i].w;
			re++;
			for(j=i+1;j<n;j++){
				if(used[j]){
					continue;
				}
				if(s[j].l>=l&&s[j].w>=w){
					used[j]=1;
					l=s[j].l;
					w=s[j].w;
				}
			}
		}
		printf("%d\n",re);
	}
	return 0;
}