#include <iostream>
using namespace std;

struct data
{
	int w,l;
}stick[5010];

int cmp(void const *a,void const *b)
{
	data *x,*y;
	x=(data *)a;
	y=(data *)b;
	if(x->w==y->w) return (x->l-y->l);
	else return (x->w-y->w);
}

int main()
{
	//freopen("a.in","r",stdin);
	int t;
	int i,j;
	bool b[5010];
	cin>>t;
	while(t--)
	{
		int n;
		memset(stick,0,sizeof(stick));
		cin>>n;
		for(i=0;i<n;i++)
			cin>>stick[i].l>>stick[i].w;
		qsort(stick,n,sizeof(data),cmp);
		int res=0;
		i=0;
		memset(b,false,sizeof(b));
			for(i=0;i<n;i++)
				if(b[i]) continue;
				else 
				{
					res++;
					int l=stick[i].l;
					for(j=i+1;j<n;j++)
						if(stick[j].l>=l){b[j]=true;l=stick[j].l;}
				}
		printf("%d\n",res);
	}
	return 0;
}

• Re:WA？不知道怎么回事。贪心策略和大家一样，排序也按关键字排序的。不解 (868) cgxinyan 2009-02-22 03:13:00
  • Re:WA？不知道怎么回事。贪心策略和大家一样，排序也按关键字排序的。不解 (6) wxq 2009-07-19 19:21:39