(贪心5.2.3)POJ 1065 Wooden Sticks(利用数据有序化来进行贪心选择)

/* * POJ_1064.cpp * *  Created on: 2013年10月10日 *      Author: Administrator */#include <iostream>#include <cstdio>using namespace std;const int maxn = 5010;struct node{int l,w;bool isUsed;bool operator>(node &n){return l > n.l ||(l == n.l && w > n.w);}node& operator=(node &n){l = n.l , w = n.w , isUsed = n.isUsed;return *this;}void swap(node& n){node tmp = *this;*this = n;n = tmp;}}A[maxn];int main(){int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);int i;for(i = 0 ; i < n ; ++i){scanf("%d%d",&A[i].l,&A[i].w);A[i].isUsed = false;}int j,k;for(j = 1; j < n ; ++j){for(k = 1 ; k <= n - j ; ++k){if(A[k-1] > A[k]){A[k-1].swap(A[k]);}}}node cur = A[0];A[0].isUsed = true;int c = 0;while(true){for(j = 1 ; j < n ; ++j){if(A[j].isUsed == false ){if(A[j].l >= cur.l && A[j].w >= cur.w){A[j].isUsed = true;cur = A[j];}}}c++;for(j = 1 ; j < n ; ++j){if(A[j].isUsed == false){cur = A[j];A[j].isUsed = true;break;}}if(j == n){break;}}printf("%d\n",c);}return 0;}