pku 3277 source.cpp

POJ 3277 city horizon代码 HEAP的应用.

//PKU 3277 Source 

#include<iostream>
#include<fstream>
#include<queue>
#include<algorithm>
using namespace std;

struct node{
//	long index;
	long beg;
	long end;
	long height;
};

struct position{
	bool tp;//=0 start =1 end
	long pos;
	long index;
};
position pos[100000];
node build[100000];
long cnt=0;
long n;

bool cmpp(position a,position b)
{
	if(a.pos==b.pos){
		return a.tp>b.tp;
	}
	return a.pos<b.pos;
}

bool cmpb(node a,node b)
{
	if(a.beg==b.beg)
		return a.end<b.end;
	return a.beg<b.beg;
}
class cmp{

public:
	bool operator()(const node&,const node&) const;
};

bool cmp::operator ()(const node& a,const node& b) const
{
	if(a.height==b.height)
		return a.end<b.end;
	return a.height<b.height;
}
priority_queue<node,vector<node>,cmp> H;


void solve()
{
	long i;cnt=0;
	for(i=0;i<n;i++){
		scanf("%ld%ld%ld",&build[i].beg,&build[i].end,&build[i].height);
		pos[cnt].index=i;pos[cnt].tp=0;pos[cnt].pos=build[i].beg;cnt++;
		pos[cnt].index=i;pos[cnt].tp=1;pos[cnt].pos=build[i].end;cnt++;
	}
	sort(pos,pos+cnt,cmpp);
	__int64 total=0;__int64 prex=0;__int64 ch=0;
	for(i=0;i<cnt;i++){
		if(pos[i].tp==1){
			while(!H.empty()){
				node tmp=H.top();
				if(tmp.end<=pos[i].pos){
					H.pop();
					total+=ch*(pos[i].pos-prex);
					prex=pos[i].pos;ch=0;
					if(!H.empty()){
						tmp=H.top();ch=tmp.height;
					}
				}
				else{
					break;
				}
			}
		}
		else{
			long in=pos[i].index;
			H.push(build[in]);node tmp=H.top();
			total+=ch*(pos[i].pos-prex);
			ch=tmp.height;prex=pos[i].pos;
		}
	}

	printf("%I64d\n",total);
}
int main()
{

//	freopen("input.in","r",stdin);
	long i;
	cin>>n;
	solve();
	return 0;
}