3615791_tle.cpp

北大大牛代码 1240道题的原代码 超级权威

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

struct node
{
	int w, h;
}doll[20001];

int cmp(const void*a,const void*b)
{
    if((*(node*)a).w==(*(node*)b).w)
        return (*(node*)b).h-(*(node*)a).h;
    return (*(node*)a).w-(*(node*)b).w;
}

void input()
{
	int n, i, j, t, ans;
	int mark[20001];

	memset(mark,0,sizeof(mark));
	scanf("%d",&n);
	for(i = 0; i < n; i++)
		scanf("%d%d",&doll[i].w,&doll[i].h);
	qsort(doll,n,sizeof(doll[0]),cmp);
	ans = 0;
	for(i = 0; i < n; i++)
	{
		if(mark[i])
			continue;
		t = i;
		for(j = i+1; j < n; j++)
		{
			if(!mark[j]&&doll[j].w>doll[t].w&&doll[j].h>doll[t].h)
			{
				mark[j] = 1;
				t = j;
			}
		}
		ans++;
	}
	printf("%d\n",ans);
}

int main()
{
	int t;

	scanf("%d",&t);
	while(t--)
		input();
	return 0;
}