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コード:
テーマ分析:ええと、このカードは、関数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;
}