hdoj/section3-5/section3-5.cpp

// section35.cpp: 定义控制台应用程序的入口点。

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;


struct Wooden {
    int length;
    int weight;
    string status;
};

const string CURRENT = "current";
const string DELETED = "delete";

bool compare(Wooden a, Wooden b) {
    if (a.length == b.length) {
        return a.weight < b.weight;
    }
    return a.length < b.length;
}

int calc(vector<Wooden> woodens) {
    int size = woodens.size();
    sort(woodens.begin(), woodens.end(), compare);

    int cost = 0;
    int index = -1, next = size + 1;
    Wooden node;
    for (int i = 0; i < size; i++) {
        if (CURRENT != node.status) {
            if (DELETED == woodens.at(i).status) {
                continue;
            } else {
                woodens.at(i).status = CURRENT;
                index = i;
                cost++;
                node = woodens.at(i);
                if (i == (size - 1)) {
                    break;
                }
            }
        }

        if (CURRENT == woodens.at(i).status || DELETED == woodens.at(i).status) {
        } else {
            if (woodens[i].length >= node.length && woodens[i].weight >= node.weight) {
                woodens[index].status = DELETED;
                woodens[i].status = CURRENT;
                index = i;
                node = woodens[i];
            } else if (i < next) {
                next = i;
            }
        }
        if (i == (size - 1)) {
            woodens[index].status = DELETED;
            index = -1;
            i = next - 1;
            node = Wooden{0, 0};
            next = size + 1;
        }
    }
    return cost;
}

int main() {
    int T, n;
    vector<Wooden> woodens;
    int l, w;
    while (cin >> T) {
        for (int i = 0; i < T; i++) {
            cin >> n;
            for (int j = 0; j < n; j++) {
                cin >> l >> w;
                woodens.push_back(Wooden{l, w, ""});
            }
            cout << calc(woodens) << endl;
            woodens.clear();
        }
    }
    return 0;
}