// section35.cpp: 定义控制台应用程序的入口点。 #include #include #include #include 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 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 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; }