1065.cpp

来自「The output should contain the minimum se」· C++ 代码 · 共 72 行

#include <iostream>
#include <algorithm>

#define BUFSIZE		10240

using namespace std;

struct Stick
{
	int	l, w;
	bool	in;
};

Stick	sticks[BUFSIZE];

bool compare(const Stick &x, const Stick &y);

int
main(int argc, char *argv[])
{
	int	t;
	cin >> t;
	
	int	n;
	while (--t >= 0)
	{
		cin >> n;
		for (int i = 0; i < n; ++i)
		{
			cin >> sticks[i].l >> sticks[i].w;
			sticks[i].in = false;
		}
		
		sort(sticks, sticks + n, compare);
		
		int	count = 0;
		int	i = 0;
		while (i != n)
		{
			if (!sticks[i].in)
			{
				++count;
				int	j = i, k = i;
				while (j != n)
				{
					if (!sticks[j].in && sticks[k].l <= sticks[j].l && sticks[k].w <= sticks[j].w)
					{
						k = j;
						sticks[j++].in = true;
					}
					else
						++j;
				}
			}
			else
				++i;
		}
		
		cout << count << endl;
	}
		
	return 0;
}

bool
compare(const Stick &x, const Stick &y)
{
	if (x.l != y.l)
		return x.l < y.l;
	return x.w < y.w;
}