1025.cpp

zju 1025 Wooden Sticks http://acm.zju.edu.cn/show_problem.php?pid=1025

#include <iostream>
using namespace std;
void px(int l[],int w[],int n)
{
	int tl,tw,i,j;
	for (i=0;i<n;i++)
		for (j=i+1;j<n;j++)
			if ( (l[i]>l[j]) || (l[i]==l[j] && w[i]>w[j]) )
			{
				tl=l[i];l[i]=l[j];l[j]=tl;
				tw=w[i];w[i]=w[j];w[j]=tw;
			}
}
void work(int l[],int w[],int n,int &a)
{
	int i=0,j=1,l1[5000],w1[5000],m=0;
	while (i<n-1 && j<n)
	{
		if (w[i]<=w[j]) {i=j;j++;}
		else 
		{
			l1[m]=l[j];
			w1[m]=w[j];
			m++;
			j++;
		}
	}
	a++;
	if (m!=0) work(l1,w1,m,a);
}
int main()
{
	int a,i,j,t,n,l[5000],w[5000];
	cin>>t;
	for (i=0;i<t;i++)
	{
		cin>>n;
		for (j=0;j<n;j++)
			cin>>l[j]>>w[j];
		px(l,w,n);
		a=0;
		work(l,w,n,a);
		cout<<a<<endl;
	}
	return(0);
}