记录编号	43385	评测结果	AAAAA
题目名称	1125.木棍	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.380 s
提交时间	2012-10-10 08:57:52	内存使用	3.21 MiB

#include <iostream>
#include <cstdio>
using namespace std;

int l[5010],w[5010],rec[5010];
bool used[5010];

void swap(int& a,int& b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}

int main(void)
{
	freopen("wooden.in","r",stdin);
	freopen("wooden.out","w",stdout);
	int i,j,n,rest,c=0,from,temp,temp2;
	cin>>n;
	rest=n;
	for (i=1;i<=n;i++)
	{
		cin>>l[i]>>w[i];
		l[i]--;
		w[i]--;
		rec[i]=l[i]*10000+w[i];
	}
	for (i=1;i<n;i++)
		for (j=1;j<=n-i;j++)
			if (rec[j]>rec[j+1])
			{
				swap(l[j],l[j+1]);
				swap(w[j],w[j+1]);
				swap(rec[j],rec[j+1]);
			}
	while (rest)
	{
		c++;
		for (i=1;i<=n;i++)
			if (!used[i])
			{
				from=i;
				break;
			}
		used[from]=true;
		temp=l[from];
		temp2=w[from];
		rest--;
		for (i=from+1;i<=n;i++)
		{
			if (used[i])
				continue;
			if (temp<=l[i]&&temp2<=w[i])
			{
				used[i]=true;
				temp=l[i];
				temp2=w[i];
				rest--;
			}
		}
	}
	cout<<c<<endl;
	return(0);
}