比赛 20121009 评测结果 AAAAA
题目名称 木棍 最终得分 100
用户昵称 Makazeu 运行时间 0.015 s
代码语言 C++ 内存使用 2.00 MiB
提交时间 2012-10-09 19:46:00
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <algorithm> 
#include <cstring>
#include <string>
using namespace std;
const int MAXN=5011;
class Wood{public:int len,wei;}W[MAXN];
int N,ans=0,now,nlen,nwei; bool flag[MAXN]={0};

bool cmp(const Wood&a,const Wood&b)
{
	if(a.len!=b.len) return a.len<b.len;
	return a.wei<b.wei;
}

inline void init()
{
	scanf("%d\n",&N);
	for(int i=1;i<=N;i++)
		scanf("%d %d\n",&W[i].len,&W[i].wei);
	sort(W+1,W+1+N,cmp);
}

inline void work()
{
	for(int i=1;i<=N;i++)
	{
		if(flag[i]) continue; flag[i]=1;
		nlen=W[i].len,nwei=W[i].wei;
		for(int j=i+1;j<=N;j++)
		{
			if(flag[j]) continue;
			if(W[j].len<nlen || W[j].wei<nwei) continue;
			flag[j]=1; nlen=W[j].len,nwei=W[j].wei;
		} ans++;
	}
	printf("%d\n",ans);
} 

int main()
{
	freopen("wooden.in","r",stdin);
	freopen("wooden.out","w",stdout);
	init();work();
	return 0;
}