杭电 hdu 1051 Wooden Sticks

贪心问题，不过错了几次，我先将数据按重量进行排序，同时把重量相同的按长度进行排序。然后每处理一个木头，就向后搜索，查找所有可以符合题意的木头。并将已处理的木头进行标记，避免重复查找。

/* THE ROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//

        URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1051
        Name  : Wooden Sticks

        Date  : Wednesday, April 20, 2010
        Time Stage :

        Result:
3846516 2011-04-20 23:26:42 Accepted 1051 46MS 344K 2469 B C++ pyy

Test Data:

Sample Input
99
4
2 1
9 2
5 4
8 5

4
9 1
8 2
6 2
5 2

4

9 2
8 2
6 2
5 2

Sample Output
2
2
1

//----------------------------------------------------------------------------*/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
struct node
{
        int len, wei;
};
void swap( node & lhs, node & rhs )
{
        node tmp = lhs;
        lhs = rhs;
        rhs = tmp;
}

node wood[5005];
int n, times;
int hash[5005];

void out()
{
        int i, j;
        for( i = 0; i < n; i++ )
                printf("(%d, %d) ", wood[i].len, wood[i].wei );
        puts("/n");
}

void psort()
{
        int i, j, k;
        int pmin, ipmin;
        for( i = 0; i < n; i++ )
        {
                ipmin = n - 1;
                for( j = i; j < n; j++ )
                        if( wood[j].wei < wood[ipmin].wei || ( wood[j].wei == wood[ipmin].wei && wood[j].len < wood[ipmin].len ) )
                                ipmin = j;
                swap( wood[i], wood[ipmin] );
        }
}
void process()
{
        memset( hash, 0, sizeof( hash ) );
        int i, j, k;
        times = 0;
        for( i = 0; i < n; i++ )
        {
                if( hash[i] )
                        continue;
                ++times;
                for( j = i + 1, k = i; j < n; j++ )
                {
                        if( !hash[j] && wood[k].len <= wood[j].len )
                        {
                                k = j;
                                hash[j] = 1;
                        }
                }
        }
}

int main( void )
{
        int i, j, k;
        int tcase;
        while( cin >> tcase )
        {
                while( tcase-- )
                {
                        cin >> n;
                        for( i = 0; i < n; i++ )
                                cin >> wood[i].len >> wood[i].wei;
                        psort();
                        process();
                        cout << times << endl;
                }
        }
        return 0;
}