2016级算法第一次练习赛-E.AlvinZH的儿时回忆——蛙声一片
2024-08-22 07:19:25
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);
}
}
最新文章
- 李洪强iOS经典面试题156 - Runtime详解(面试必备)
- 如何正确选择UI自动化测试
- hdu 1860统计字符
- 模拟---LCR
- GCD的基本使用
- NDK环境配置
- 151111 sqlite3数据库学习
- c++,多继承造成的二义性及解决办法
- expdp时遇到ORA-31693&;amp;ORA-02354&;amp;ORA-01466
- Rigidbody(刚体) and Collider(碰撞器)
- Java垃圾回收机制[转]
- Thymeleaf利用layout.html文件生成页面布局框架
- mysql之limit使用
- Modbus协议栈实现Modbus RTU多主站支持
- Visual Studio 2013 编译 64 位 Python 的 C 扩展 (使用 PyObject 包装)
- 华为机型cordova-plugin-image-picker读取图库闪退
- ABS PBT POM材质键冒
- Memcached学习一:Memcached安装使用
- VMware虚拟机三种联网方法及原理
- css 边框颜色渐变的半圆
热门文章
- C#在控制台输出异常所在的行数
- 创建一个实例&;创建一个线程。。
- code4511 信息传递
- Linux useradd 与 adduser的区别, /sbin/nologin 与 /bin/bash
- redis 缓存用户账单策略
- js教程系列32 :javascript-DOM节点操作
- CodeForces 682C Alyona and the Tree (树上DFS)
- ORB_SLAM2_Android
- javascript的caller,callee,call,apply[转]
- 关于linq to sql调用存储过程,出现";无法枚举查询结果多次";的问题