题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1896
题目大意:
有n个石头,每个石头有:p 它所在的位置 ,d 它能扔多远
从0 开始,遇到第奇数个石头就扔出去,否则则无视,如果同一位置多个石头,则先遇到扔得近的,问最远的石头在什么位置。
采用优先队列。
奇数则p=p+d,弹出,再重新放入,偶数则直接弹出,输出最后一个石头所在的位置。
优先队列:
empty() 如果队列为空返回真
pop() 删除对顶元素
push() 加入一个元素
size() 返回优先队列中拥有的元素个数
top() 返回优先队列对顶元素
在默认的优先队列中,优先级高的先出队。在默认的int型中先出队的为较大的数。
使用方法:
头文件:
声明方式:
1、普通方法:
2、自定义优先级:
3、结构体声明方式:
1 #include <iostream> 2 #include <queue> 3 #include <stdio.h> 4 using namespace std; 5 class stone 6 { 7 public: 8 int p; 9 int d; 10 friend bool operator < (stone a,stone b) //运算符重载 重载“<“ 11 { 12 if(a.p==b.p) 13 return a.d>b.d; 14 else 15 return a.p>b.p; 16 } 17 }; 18 priority_queue<stone>s; //定义优先列队 19 int main() 20 { 21 int T,n,i,max; 22 stone x; 23 scanf("%d",&T); 24 while(T--) 25 { 26 scanf("%d",&n); 27 for(i=1;i<=n;i++) 28 { 29 scanf("%d %d",&x.p,&x.d); 30 s.push(x); 31 } 32 i=1; //统计奇偶 33 while(!s.empty()) 34 { 35 if(i&1) //奇数 36 { 37 x=s.top(); //返回队顶元素 38 s.pop(); //弹出 39 x.p=x.p+x.d; 40 s.push(x); 41 } 42 else 43 { 44 max=s.top().p; 45 s.pop(); 46 } 47 i++; 48 } 49 printf("%d\n",max); 50 } 51 return 0; 52 }
原文:http://www.cnblogs.com/riddle/p/3567735.html