HDU (1896 Stones 经典的优先队列的应用)

spoiler posted @ 2011年5月11日 02:58 in STL有关的题目 , 2436 阅读

题目意思:路上有很多石头,当你遇到奇数序列的石头就把他向前仍,偶数的不动他,如果两个石头一起,先考虑可以仍的比较近的石头仍也就是比较大的石头,这样一直下去,直到前面所有的石头都不可以仍了为止,题目意思理解了好久才理解对!

题目分析:这题用优先队列非常方便,这里稍微介绍优先队列,优先队列可以自动把存储在里面的每个元素按从大到小的排列,然后,你需要用重载,把里面的元素按位置坐标从小到大的排列,这样没就可以模拟石头的动态位置了,仍完一个就把这个的信息更新,位置信息改变要,如果是偶数个那么直接出队列就可以了,

代码:

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
struct node{
	int pos;
	int dis;
};
struct cmp{
	bool operator () (node a,node b){
		if(a.pos!=b.pos)
			return a.pos>b.pos;
		else
			return a.dis>b.dis;
	}
};
int main(){
	priority_queue<node,vector<node>,cmp> s;
	node t;
	int cas,n;
	int car,flag,result;
	while(scanf("%d",&cas)!=EOF){
		while(cas--){
			scanf("%d",&n);
			while(n--){
				scanf("%d %d",&t.pos,&t.dis);
				s.push(t);
			}
			flag=true;
			car=-1;
			while(!s.empty()){
				t=s.top();
				s.pop();
				if(flag){
					flag=false;
					t.pos+=t.dis;
					s.push(t);
				}
				else
					flag=true;
				result=t.pos;
			}
			printf("%d\n",result);
		}
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter