hdoj/section3-5/section3-5.cpp

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

#include"stdafx.h"

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


struct Wooden
{
	int length;
	int weight;
};

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

int calc(vector<Wooden> woodens) {
	int cost = 0;
	int size = woodens.size();
	int index = 0;
	for (; size != 0; ) {
		if (size == 1) {
			cost++;
			break;
		}
		sort(woodens.begin(), woodens.end(), compare);
		Wooden node = woodens[0];

		for (int i = 1; i < size; i++) {
			if (woodens.at(i).length < node.length || woodens.at(i).weight < node.weight) {
				woodens.erase(woodens.begin());
				break;
			}
			woodens.erase(woodens.begin() + i);
			size = woodens.size();
		}
	}
	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;
}