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 100005 using 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);
}
}
05-11 01:16