C++编程 hdu 1065（贪心题目）

There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows: 

(a) The setup time for the first wooden stick is 1 minute. 
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l' and weight w' if l<=l' and w<=w'. Otherwise, it will need 1 minute for setup. 

You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are (4,9), (5,2), (2,1), (3,5), and (1,4), then the minimum setup time should be 2 minutes since there is a sequence of pairs (1,4), (3,5), (4,9), (2,1), (5,2).

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n , 1<=n<=5000, that represents the number of wooden sticks in the test case, and the second line contains n 2 positive integers l1, w1, l2, w2, ..., ln, wn, each of magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.

The output should contain the minimum setup time in minutes, one per line.

3 
5 
4 9 5 2 2 1 3 5 1 4 
3 
2 2 1 1 2 2 
3 
1 3 2 2 3 1

2
1
3

#include <iostream>
using namespace std;
int n;
struct wooden
{int l;int w;int no;
};wooden wood[5001];
void init()
{int i;for(i = 0; i < 5001; i ++){wood[i].l = 0;wood[i].w = 0;wood[i].no = -1;}}bool compare(int i, int j)
{if(wood[i].l >= wood[j].l && wood[i].w >= wood[j].w)return true;else if(wood[i].l <= wood[j].l && wood[i].w <= wood[j].w)return true;elsereturn false;
}void check()
{int i;for(i = 0; i < n; i++){cout << "(" << wood[i].l <<","<< wood[i].w <<"," << wood[i].no <<") ";}
}//int doit()
//{
//    int i;
//    int m = 1;
//    for(i = 0; i < n - 1; i++)
//    {
//        if(compare(i, i + 1))
//        {
//            m ++;
//        }
//    }
//    return m;
//}int main()
{int t, cur, w;int i, j;cin >> t;while(t--){cin >> n;init();for(i = 0; i < n; i++)cin >> wood[i].l >> wood[i].w;for(i = 0; i < n; i ++){for(j = 0; j < n - i - 1; j++){if(wood[j].l > wood[j+1].l){swap(wood[j], wood[j+1]);}}}//        for(i = 0; i < n; i ++)
//        {
//            for(j = 0; j < n - i - 1; j++)
//            {
//                if(wood[j].w > wood[j+1].w)
//                    swap(wood[j], wood[j+1]);
//            }
//
//        }
//        }cur = 0;for(i = 0; i < n; i++){if(wood[i].no == -1){cur ++;w = wood[i].w;wood[i].no = cur;for(j = i; j < n; j++){if(wood[j].no == -1 && w <= wood[j].w){wood[j].no = cur;w = wood[j].w;}}}
//            check();
//                cout << endl;}cout << cur << endl;}return 0;
}

大水题。。但是做的时候出了问题 = =。一开始的想法是根据l排一次序，再根据w排一次序。。这是不行的，原因如下。。

可能出现这种情况（7，8），（8, 7），（9,10），（10,9），（11，11）

类似于如上情况就行不通了。。doit（）注释掉的就是之前错的算法= =。。看别人说的分集合恍然大悟。。遂写成。。唉，这下惨了。。水题做成这个样子。。