864 AlvinZH的儿时回忆----蛙声一片

题目链接：https://buaacoding.cn/problem/865/index

思路

中等题。难点在于理解题意！仔细读题才能弄懂题目规则。整个过程是通过模拟位置变化进行的。

第一个问题是AlvinZH的情绪变化，忽略某一位置的青蛙条件是：刚刚经历失败，即前一位置没有抓到青蛙。

第二个问题是什么情况抓到青蛙：不灰心的情况遇到多只青蛙，除去跳的最远的青蛙（可能多只），剩下的都被抓。

分析

像这种数据循环利用且不断变化，但是有序的数据集，应该想到使用优先队列。优先队列可以保证所有青蛙按一定顺序排列。

有些同学使用优先队列数组，有点浪费空间。这里只需要一个优先队列即可，具体可看代码注释。

考点：优先队列。

难点：分析出各种情况，不能乱，逻辑要清晰。

参考代码

// // Created by AlvinZH on 2017/9/29. // Copyright (c) AlvinZH. All rights reserved. //#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #define MaxSize 100005using namespace std;struct Frog {int pos;//位置int dis;//跳程bool operator < (const Frog& f) const {if(pos != f.pos) return pos > f.pos;//小值优先return dis < f.dis;//大值优先} };int main() {int T, n;Frog nowF;scanf("%d", &T);while (T--){scanf("%d", &n);priority_queue<Frog> Q;for (int i = 0; i < n; i++) {scanf("%d %d", &nowF.pos, &nowF.dis);Q.push(nowF);}int numF = 0;bool Fail = false;//初始不灰心while (!Q.empty()){nowF = Q.top();//距离最近且跳的最远的青蛙Q.pop();if(!Fail){Fail = true;Frog nextF = Q.top();while (!Q.empty() && nextF.pos == nowF.pos)//存在多只{Q.pop();if(nextF.dis == nowF.dis)//比翼双飞{nextF.pos += nextF.dis;Q.push(nextF);}else//抓住它{numF++;Fail = false;}nextF = Q.top();}nowF.pos += nowF.dis;Q.push(nowF);}else//一起忽略，记得pop这些青蛙{Fail = false;Frog nextF = Q.top();while (!Q.empty() && nextF.pos == nowF.pos){Q.pop();nextF = Q.top();}}}printf("%d %d\n", nowF.pos, numF);} }

转载于:https://www.cnblogs.com/AlvinZH/p/7698978.html

总结

以上是生活随笔为你收集整理的2016级算法第一次练习赛-E.AlvinZH的儿时回忆——蛙声一片的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。