1562.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1562 on 2006-03-15 at 19:40:19 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 10240;

class Block {
public:
	int l, m;
	void make();
	bool operator <(const Block&) const;
};
void Block::make() {
	scanf("%d %d", &l, &m);
}
bool Block::operator <(const Block& b) const {
	if(l != b.l) return l < b.l;
	else return m < b.m;
}

int main()
{
	Block block[MAX];
	int i, n, h[MAX];
	
	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 0; i < n; i++) block[i].make();
		sort(block, block+n); int len = 0;
		for(i = 0; i < n; i++) {
			int *o = upper_bound(h, h+len, block[i].m);
			*o = block[i].m;
			if(o - h == len) len++;
		}
		printf("%d\n", len);
	}
	printf("*\n");
	
	return 0;
}