pku1065.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <stdlib.h>

typedef struct 
{
	int l, w;
} Stick;

Stick s[5000];
int st[5000];
int cnt, N;

int cp(const void *a, const void *b)
{
	Stick *aa = (Stick *)a;
	Stick *bb = (Stick *)b;

	if (aa->l != bb->l)
	{
		return bb->l - aa->l;
	}
	return bb->w - aa->w;
}

int main()
{
	int T, i, w, l;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &N);
		for (i = 0; i < N; i++)
		{
			scanf("%d%d", &s[i].l, &s[i].w);
			st[i] = 0;
		}
		qsort(s, N, sizeof(s[0]), cp);
		cnt = 0;
		while (1)
		{
			i = 0;
			while (i < N && st[i])
			{
				i++;
			}
			if (i == N)
			{
				printf("%d\n", cnt);
				break;
			}
			st[i] = 1;
			w = s[i].w;
			l = s[i].l;
			while (i < N)
			{
				if (!st[i] && s[i].w <= w && s[i].l <= l)
				{
					st[i] = 1;
					w = s[i].w;
					l = s[i].l;
				}
				i++;
			}
			cnt++;
		}
	}
	return 0;
}