hdoj/section3-5/section3-5.cpp

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

#include"stdafx.h"

#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) {
	return (a.length < b.length) && (a.weight < b.weight);
}

int calc(vector<Wooden> woodens) {
	int size = woodens.size();
	if (size == 0) {
		return 0;
	}
	if (size == 1) {
		return 1;
	}

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

		if (CURRENT == woodens.at(i).status) {
			continue;
		}
		if (woodens.at(i).length >= node.length && woodens.at(i).weight >= node.weight) {
			woodens.at(i).status = DELETED;
			continue;
		}
		if (woodens.at(i).length <= node.length &&woodens.at(i).weight <= node.weight) {
			woodens.at(index).status = DELETED;
			woodens[i].status = CURRENT;
			node = woodens[i];
			index = i;
			i = -1;
			continue;
		}
		if (i == (size - 1)) {
			woodens.at(index).status = DELETED;
			index = -1;
			node = Wooden{};
		}
	}
	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;
}