原题: http://acm.nyist.net/JudgeOnline/problem.php?pid=236
同样题目poj1065 Wooden Sticks http://poj.org/problem?id=1065
//将木棍先按l由小到大排序,再按w排序,最后遍历即可. #include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct M { int l; int w; }m[5010]; int cmp(M a,M b) { if(a.l!=b.l){ return a.l<b.l; }else{ return a.w<b.w; } } int main() { int t; scanf("%d",&t); while(t--) { int i,n; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d %d",&m[i].l,&m[i].w); } sort(m,m+n,cmp); int ans=1; int l=m[0].l; int w=m[0].w; while(true) { for(i=1;i<n;i++) { if(m[i].l==-1)continue; if(m[i].l>=l && m[i].w>= w) { l=m[i].l; w=m[i].w; m[i].l=-1; } } // l=-1; for(i=1;i<n;i++) { if(m[i].l!=-1) { l=m[i].l; w=m[i].w; break; } } if(i==n)break; ans++; } printf("%d\n",ans); } return 0; } //AC