题意:就是一条直线上面有很多石头。石头有初始位置跟能扔的距离,如果是奇数石头,那么就扔,否则,就在原位置不管。问最远石头距离起点的位置是多少。
思路:对于这个题目,偶数石头我们就不管了,奇数石头我们需要再次使用的,那么我们很容易想到优先队列。
#include <bits/stdc++.h>
using namespace std;
struct node{
int pos,dis;
friend bool operator<(node a,node b){
if(a.pos!=b.pos)
return a.pos>b.pos;//最小值优先
else return a.dis>b.dis;
}
};
int main(){
int t;
while(cin>>t){
while(t--){
int n;
cin>>n;
priority_queue<node>q;
node a,b;
for(int i=0;i<n;i++){
int c,d;
cin>>c>>d;
a.pos=c;
a.dis=d;
q.push(a);
}
int z=0;
int sum=0;
while(!q.empty()){
z++;
a=q.top();
sum=a.pos;
if(z%2==0){
q.pop();
}
else{
b.pos=a.pos+a.dis;
b.dis=a.dis;
q.pop();
q.push(b);
}
}
cout<<sum<<endl;
}
}
return 0;
}