HDU 4302 Contest 1

维护两个优先队列即可。要注意，当出现蛋糕的位置刚好在狗的位置时，存在右边。

注意输出大小写。。。

#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;

struct RP{
	int pos;
	bool operator < (const RP &t)const{
		if(pos>t.pos) return true;
		return false;
	}
};
struct LP{
	int pos;
	bool operator < (const LP &t)const{
		if(pos<t.pos) return true;
		return false;
	}
};

priority_queue<LP>LeftPush;
priority_queue<RP>RightPush;
LP tmpL;
RP tmpR;

void Clear(){
	while(!LeftPush.empty())
	LeftPush.pop();
	while(!RightPush.empty())
	RightPush.pop();
}

int main(){
	int T,P,N,POS,kase=0;
	int op,position;
	int direct,left,right;
	bool flagL,flagR;
	scanf("%d",&T);
	int ans;
	while(T--){
		Clear();
		POS=0;
		direct=1;
		ans=0;
		scanf("%d%d",&P,&N);
		while(N--){
			scanf("%d",&op);
			if(!op){
				scanf("%d",&position);
				if(position>=POS){
					tmpR.pos=position;
					RightPush.push(tmpR);
				}
				else if(position<POS){
					tmpL.pos=position;
					LeftPush.push(tmpL);
				}
			}
			else{
				flagR=flagL=false;
				if(!RightPush.empty()){
					flagR=true;
					tmpR=RightPush.top();					
				}
				if(!LeftPush.empty()){
					flagL=true;
					tmpL=LeftPush.top();
				}
				if(!flagR&&!flagL){
				//	direct=-1;
					continue;
				}
				else if(!flagR&&flagL){
					direct=-1;
					ans+=(POS-tmpL.pos);
					POS=tmpL.pos;
					LeftPush.pop();
				}
				else if(flagR&&!flagL){
					direct=1;
					ans+=(tmpR.pos-POS);
					POS=tmpR.pos;
					RightPush.pop();
				}
				else{
					left=POS-tmpL.pos;
					right=tmpR.pos-POS;
					if(right<left){
						direct=1;
						ans+=right;
						RightPush.pop();
						POS=tmpR.pos;
					}
					else if(left<right){
						ans+=left;
						direct=-1;
						LeftPush.pop();
						POS=tmpL.pos;
					}
					else {
						if(direct>0){
							direct=1;
							ans+=right;
							RightPush.pop();
							POS=tmpR.pos;
						}
						else{
							ans+=left;
							direct=-1;
							LeftPush.pop();
							POS=tmpL.pos;
						}
					}
				}
			}
		}
		printf("Case %d: %d
",++kase,ans);
	}
	return 0;
}