1537.cpp

来自「这是哈尔滨工业大学acmOJ的源代码」· C++ 代码 · 共 42 行

/*  This Code is Submitted by wywcgs for Problem 1537 on 2006-08-22 at 10:32:02 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1024;

class Elephant {
public:
	int w, iq, o;
	void make(int i) { o = i; scanf("%d %d", &w, &iq); }
	bool operator <(const Elephant&) const;
};
bool Elephant::operator <(const Elephant& e) const {
	if(w != e.w) return w > e.w;
	else return iq > e.iq;
}

int main()
{
	Elephant e[N];
	int n, prev[N];

	while(scanf("%d", &n) != EOF) {
		for(int i = 0; i < n; i++) e[i].make(i);
		sort(e, e+n);
		int len = 1, s[N], so[N];
		s[0] = -1; so[0] = -1;
		for(int i = 0; i < n; i++) {
			int* p = lower_bound(s, s+len, e[i].iq);
			*p = e[i].iq; so[p-s] = i;
			prev[i] = so[p-s-1];
			if(p-s == len) len++;
		}
		printf("%d\n", len-1);
		for(int i = so[len-1]; i != -1; i = prev[i])
			printf("%d\n", e[i].o+1);
	}
	
	return 0;
}