POJ-1065-Wooden Sticks-贪心-多关键字排序

第一次用STL的sort进行多关键字进行排序。

另外，排序后再如何处理，有一定难度。

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 5000;

/* Stick类 */
class Stick {
 public:
    int length; //长度
    int weight; //重量
    bool isProcessed; //标示“是否已处理过”
};

/*传入sort函数，表示排序规则*/
bool cmp(const Stick& stick1, const Stick& stick2) {
    /*if(stick1.length < stick2.length) {
        return true;
    } else if(stick1.length ==stick2.length) {
        if(stick1.weight < stick2.weight)
            return true;
        else
            return false;
    } else {
        return false;
    }*/
    /*先比较长度，若长度小则返回true；若长度相等，则重量小返回true;其余的返回false*/
    return stick1.length < stick2.length ||
        (stick1.length == stick2.length && stick1.weight < stick2.weight);
}

int main()
{
    Stick sticks[MAX];

    int nCases;
    cin >> nCases;

    while(nCases--) {
        int n;
        cin >> n;

        /*初始化*/
        int l, w;
        for(int i = 0; i < n; ++i) {
            cin >> l >> w;
            sticks[i].length = l;
            sticks[i].weight = w;
            sticks[i].isProcessed = false;
        }

        /*调用STL的sort进行排序*/
        sort(sticks, sticks + n, cmp);

        /*求出setup time*/
        int setupTime = 0;
        /*依次循环所有的stick*/
        for(int i = 0; i < n; i++) {
            /*若已经处理过，则继续循环*/
            if(!sticks[i].isProcessed) {
                sticks[i].isProcessed = true; //对没有处理过的stick，置“已处理过”标志
                int wCur = sticks[i].weight;  //当前stick的重量
                /*由于已对所有的sticks根据两具关键字进了排序，故只要从i+1向下判断weight的大小关系即可*/
                for(int j = i + 1; j < n; j++) {
                    /*对于还没处理过的stick且重量小的stick进行处理*/
                    if(!sticks[j].isProcessed && sticks[j].weight >= wCur) {
                        sticks[j].isProcessed = true;
                        wCur = sticks[j].weight;
                    }
                }
                setupTime++; //处理完所有不比"第i个stick的长度和重量"小的stick后，setupTime增1
            }
        }

        cout << setupTime << endl;
    }

    return 0;
}