hdu 1501

1482 ワード

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1051
テーマ分析:ええと、このカードは、関数cmpを呼び出すときにl、wをどのようにソートするかに悩んでいるからです.タイトルに与えられた意味は次のとおりです.
                   まずlを小さくして並べ替えて、lが同じならwを小さくして、最も重要なのは、lが並べ替えた後、wを見て、後のwが前のwより大きいことです.(ここに詰まっている)
その後、他の人のコードを見て、自分で分析して、やっと人がどのようにこの塵の関係を明らかにしたのかを知った.
                 最後に、出力について、一般的にはいくつかのノードがあり、例えば(4,9)、(5,2)、(2,1)、(3,5)、(1,4)の順に出力されます.
(1,4),(3,5),(4,9),    (2,1),(5,2);2つのノード、出力2
ACコード:
 
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>      
#include<iostream>
#include<algorithm>
using namespace std;
struct tt{
	int l,w;
}s[5005];
bool visit[5005];
bool cmp(const tt &a,const tt &b){
	if(a.l!=b.l)
		return a.l<b.l;
	return	a.w<b.w;
}
int main(){
	int T,i,j,n;
	cin>>T;
	while(T--){
		cin>>n;
		for(i=0;i<n;i++)
			cin>>s[i].l>>s[i].w;
		sort(s,s+n,cmp);
		memset(visit,false,sizeof(visit));
		int ans=0;
		for(i=0;i<n;i++){
			if(visit[i]) continue;
			visit[i]=true;
			ans++;
			int wmax=s[i].w;
			for(j=i+1;j<n;j++)
				if(visit[j]==false&&s[j].w>=wmax){
					visit[j]=true;
					wmax=s[j].w;
				}
		}
		cout<<ans<<endl;
	}
	return 0;
}