864 AlvinZH的兒時回憶----蛙聲一片

題目鏈接：https://buaacoding.cn/problem/865/index

思路

中等題。難點在于理解題意！仔細讀題才能弄懂題目規(guī)則。整個過程是通過模擬位置變化進行的。

第一個問題是AlvinZH的情緒變化，忽略某一位置的青蛙條件是：剛剛經(jīng)歷失敗，即前一位置沒有抓到青蛙。

第二個問題是什么情況抓到青蛙：不灰心的情況遇到多只青蛙，除去跳的最遠的青蛙（可能多只），剩下的都被抓。

分析

像這種數(shù)據(jù)循環(huán)利用且不斷變化，但是有序的數(shù)據(jù)集，應該想到使用優(yōu)先隊列。優(yōu)先隊列可以保證所有青蛙按一定順序排列。

有些同學使用優(yōu)先隊列數(shù)組，有點浪費空間。這里只需要一個優(yōu)先隊列即可，具體可看代碼注釋。

考點：優(yōu)先隊列。

難點：分析出各種情況，不能亂，邏輯要清晰。

參考代碼

// // 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;//小值優(yōu)先return dis < f.dis;//大值優(yōu)先} };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);} }

轉(zhuǎn)載于:https://www.cnblogs.com/AlvinZH/p/7698978.html

總結(jié)

以上是生活随笔為你收集整理的2016级算法第一次练习赛-E.AlvinZH的儿时回忆——蛙声一片的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。