Stones(优先队列)

╰半橙微兮° 2022-06-12 12:00 239阅读 0赞

![Image 1][]![Image 1][]

![Image 1][]

![Image 1][]原题

题意:奇数石头扔出去, 偶数石头忽略,相同位置的石头,先选择沉的,即能扔的距离比较近的。直到忽略最后一个为止,看一共走了多远。

思路:建一个优先队列,装进所有的元素,偶数石头pop掉,直到队列为空为止。

  1. #include<iostream>
  2. #include<queue>
  3. using namespace std;
  4. #define max 100000
  5. struct stone{
  6. int pos, dis;
  7. bool operator < (const stone &a) const{
  8. if(pos==a.pos)//先比较位置,位置一样比较距离。
  9. return dis>a.dis;
  10. return pos>a.pos;
  11. }
  12. };
  13. struct stone a[max], b;
  14. int main(){
  15. priority_queue<stone> q;
  16. int T, n;
  17. cin>>T;
  18. while(T--){
  19. int cnt=0, maxDis=0;
  20. cin>>n;
  21. for(int i=1; i<=n; i++)
  22. {
  23. cin>>a[i].pos>>a[i].dis;
  24. q.push(a[i]);
  25. }
  26. while(!q.empty())
  27. {
  28. maxDis=q.top().pos;
  29. if(++cnt % 2 ==0)
  30. q.pop();
  31. else
  32. {
  33. b=q.top();//奇数时,一定要先取出来,编辑完再放进去。
  34. q.pop();
  35. b.pos+=b.dis;
  36. q.push(b);
  37. }
  38. }
  39. cout<<maxDis<<endl;
  40. }
  41. return 0;
  42. }

本人语拙,不懂地方,尽请留言,如有不足,不吝赐教。

[Image 1]:

发表评论

表情:
评论列表 (有 0 条评论,239人围观)

还没有评论,来说两句吧...

相关阅读

    相关 队列优先队列

    队列 队列是一种特殊的[线性表][Link 1],特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作

    相关 优先队列

    优先队列:顾名思义,首先它是一个队列,但是它强调了“优先”二字,所以,已经不能算是一般意义上的队列了,它的“优先”意指取队首元素时有一定的选择性,即根据元素的属性选择某一项值最

    相关 优先队列

    [为什么80%的码农都做不了架构师?>>> ][80_] ![hot3.png][] 优先队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。