HDU1896 Stones————栈和队列(优先队列)

拼搏现实的明天。 2022-05-18 01:42 221阅读 0赞

Because of the wrong status of the bicycle, Sempr begin to walk east to west every morning and walk back every evening. Walking may cause a little tired, so Sempr always play some games this time.  
There are many stones on the road, when he meet a stone, he will throw it ahead as far as possible if it is the odd stone he meet, or leave it where it was if it is the even stone. Now give you some informations about the stones on the road, you are to tell me the distance from the start point to the farthest stone after Sempr walk by. Please pay attention that if two or more stones stay at the same position, you will meet the larger one(the one with the smallest Di, as described in the Input) first.  
**Input**  
In the first line, there is an Integer T(1<=T<=10)  T ( 1 <= T <= 10 ) , which means the test cases in the input file. Then followed by T test cases.  
For each test case, I will give you an IntegerN(0<N<=100,000)  N ( 0 < N <= 100 , 000 ) in the first line, which means the number of stones on the road. Then followed by N lines and there are two integers Pi(0<=Pi<=100,000)  P i ( 0 <= P i <= 100 , 000 )  and Di(0<=Di<=1,000)  D i ( 0 <= D i <= 1 , 000 )  in the line, which means the position of the i-th stone and how far Sempr can throw it.  
**Output**  
Just output one line for one test case, as described in the Description.  
**Sample Input**  
2  
2  
1 5  
2 4  
2  
1 5  
6 6  
**Sample Output**  
11  
12

--------------------

题目大意：  
玩家以直线行走，前方有n个石头  
第i  i 个石头的坐标是Pi P i  
能够扔的距离是Di  D i

以玩家为以对象，  
他碰到的**第奇数**个石头将会被他扔到距离此位置的前方Di  D i 远处  
他碰到的**第偶数**个石头将不作处理

问玩家能够走多远。

思路:  
用优先队列来存储石头，按石头的的位置从小到大，（位置相同则扔的越远，优先级越高）排列，所以我们栈顶元素肯定是离玩家最近的石头  
但是当这个位置的石头有许多个的时候，我们肯定是需要选取能扔到最远的石头啊。  
我们用优先队列来模拟这个过程，在玩家遇到最后一个石头的时候

如果最后一个石头是玩家遇到的第偶数个石头，那么玩家能够走得最远距离就是这个石头的当前的位置

如果最后一个石头是玩家遇到的第奇数个石头，那么石头肯定需要被扔一次，所以说这个石头被扔之后的位置就是玩家能够走得最距离

--------------------

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<stack>
    #include<queue>
    #include<cstring>
    #include<string>
    #include<cmath>
    using namespace std;
    
    struct node{
        int x,y;//x保存当前石头的位置，y保存该石头可以被扔多远 
        node(){}
        node(int _x,int _y)
        {
            x=_x;
            y=_y;
         } 
         bool operator < (const node & b)const //重载运算，按位置小的排序，相同位置的话扔的越远优先级越高 
         {
            return x==b.x?y>b.y:x>b.x;
         }
    };
    
    int main()
    {
        int t,n;
        int a,b;
        ios::sync_with_stdio(0); 
        cin>>t;
        while(t--)
        {
            cin>>n;
            priority_queue<node> q;//优先队列 
            for(int i=0;i<n;i++)
            {
                int x,y;
                cin>>x>>y;
                q.push(node(x,y));
            }
            node a;
            int k=1; 
            while(q.size())//直接模拟到队列为空 
            {
                a=q.top();
                q.pop();
                if(k)   q.push(node(a.x+a.y,a.y));//这个石头可以扔的话，就把它扔到路前方 
                k=!k;//奇偶变化 
            }
            cout<<a.x<<endl;
        }
        return 0;
    }