我为什么用了一个堆就过了？

/*
 * poj2528heap.cpp
 *
 *  Created on: 2012-1-20
 *      Author: dxhisboy
 */




#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using std::sort;
using std::priority_queue;
bool past[10010],show[10010];
struct event{
	int num,pos;
	bool left;
	bool operator<(const event &b)const{
		if (pos<b.pos) return true;
		if (pos>b.pos) return false;
		if (left&&!b.left) return true;
		if (!left&&b.left) return false;
		if (left&&b.left) return num>b.num;
		return num<b.num;
	}
} a[22000];
priority_queue<int> q;
int main(){
	int t;
	scanf("%d",&t);
	while (t--){
		int n;
		scanf("%d",&n);
		memset(past,0,sizeof(past));
		memset(show,0,sizeof(show));
		for (int i=1;i<=n;i++){
			scanf("%d%d",&a[i+i-1].pos,&a[i+i].pos);
			a[i+i-1].left=true;a[i+i-1].num=i;
			a[i+i].left=false;a[i+i].num=i;
		}
		sort(a+1,a+n+n+1);
		a[n+n+1].pos=-1;
		while (!q.empty()) q.pop();
		for (int i=1;i<=n+n;i++){
			if (!q.empty()&&a[i].pos!=a[i+1].pos) show[q.top()]=true;
			if (a[i].left)
				q.push(a[i].num);
			else
				past[a[i].num]=true;
			while (!q.empty()&&past[q.top()]) q.pop();
		}
		int ans=0;
		for (int i=1;i<=n;i++)
			if (show[i]) ans++;
		printf("%d\n",ans);
	}
	return 0;
}

• 呵呵，我用的set，比这个清晰点 (844) FuckYouFuckingMe 2012-02-29 11:49:30