1314.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1314 on 2005-11-02 at 22:36:47 */ 
#include <cstdio>
#include <cstring>
#include <cstdlib>

const int MAX = 5120;

class Stick {
public:
	int l;
	int w;
};

int cmp(const void*, const void*);

int main()
{
	Stick stick[MAX];
	int T, t, p, m;
	int i, j, n;
	bool cut[MAX];

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n);
		for(i = 0; i < n; i++) {
			scanf("%d %d", &stick[i].l, &stick[i].w);
		}
		memset(cut, false, sizeof(cut));
		qsort(stick, n, sizeof(Stick), cmp);
		p = 0;
		for(i = 0; i < n; i++) {
			if(!cut[i]) {
				p++;
				m = i;
				for(j = i + 1; j < n; j++) {
					if(stick[m].w <= stick[j].w && !cut[j]) {
						cut[j] = true;
						m = j;
					}
				}
			}
		}
		printf("%d\n", p);
	}
	
	return 0;
}

int cmp(const void *a, const void *b)
{
	Stick *x = (Stick*)a, *y = (Stick*)b;
	if(x->l < y->l) {
		return -1;
	} else if(x->l > y->l) {
		return 1;
	} else {
		if(x->w < y->w) {
			return -1;
		} else {
			return 1;
		}
	}
}