关键词:
个人心得:这一题在暑假集训的周测里做到过,当时就死模拟,然后卡了很久很久才做对。现在发现运用stack其实非常方便,
将向左向右游动的鱼分开,则往后走只要往右移动的就放入stack,往左的时候就与stack进行对比,以后后面的鱼是与此时左边的鱼
是没有关系的,所以可以很好的解决,
第1行:1个数N,表示鱼的数量(1 <= N <= 100000)。 第2 - N + 1行:每行两个数A[i], B[i],中间用空格分隔,分别表示鱼的大小及游动的方向(1 <= A[i] <= 10^9,B[i] = 0 或 1,0表示向左,1表示向右)。
输出1个数,表示最终剩下的鱼的数量。
5 4 0 3 1 2 0 1 0 5 0
2
1 #include<iostream> 2 #include<cstring> 3 #include<string> 4 #include<cstdio> 5 #include<vector> 6 #include<cmath> 7 #include<stack> 8 #include<queue> 9 #include<algorithm> 10 using namespace std; 11 #define in 1000000005 12 int n; 13 int u[100005],v[100005]; 14 int main() 15 { 16 cin>>n; 17 stack<int > pq; 18 for(int i=0;i<n;i++) 19 cin>>u[i]>>v[i]; 20 int sum=n; 21 for(int i=0;i<n;i++) 22 { 23 if(v[i]==1) 24 pq.push(u[i]); 25 else 26 { 27 if(pq.empty()) continue; 28 int t=pq.top(); 29 if(t>u[i]) 30 sum--; 31 else 32 { 33 while(t<u[i]) 34 { 35 sum--; 36 pq.pop(); 37 if(!pq.empty()) 38 t=pq.top(); 39 else 40 break; 41 42 } 43 if(pq.empty()) continue; 44 else if(pq.top()>u[i]) sum--; 45 46 } 47 } 48 } 49 cout<<sum<<endl; 50 return 0; 51 }
51nod1289stack
1289 大鱼吃小鱼题目来源: Codility基准时间限制:1 秒空间限制:131072 KB分值: 5 难度:1级算法题 收藏 关注有N条鱼每条鱼的位置及大小均不同,他们沿着X轴游动,有的向左,有的向右。游动的速度... 查看详情
51nod1289大鱼吃小鱼(栈模拟)
1289大鱼吃小鱼题目来源:Codility基准时间限制:1秒空间限制:131072KB分值:5难度:1级算法题收藏关注取消关注有N条鱼每条鱼的位置及大小均不同,他们沿着X轴游动,有的向左,有的向右。游动的速度是一样的,两条鱼相遇大鱼... 查看详情
51nod1289大鱼吃小鱼栈的简单模拟
传送门:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1289emmmmmm…… 大概就是……①栈空:向左右,最终必然生存(嘛~毕竟速度都是一样的,位置靠左向左游,当然追不上啦~)  ... 查看详情
小鱼的数字游戏
题目描述小鱼最近被要求参加一个数字游戏,要求它把看到的一串数字(长度不一定,以0结束,最多不超过100个,数字不超过2^32-1),记住了然后反着念出来(表示结束的数字0就不要念出来了)。这对小鱼的那点记忆力来说实在... 查看详情
洛谷p1426小鱼会有危险吗模拟/题意理解
题目描述有一次,小鱼要从A处沿直线往右边游,小鱼第一秒可以游7米,从第二秒开始每秒游的距离只有前一秒的98%。有个极其邪恶的猎人在距离A处右边s米的地方,安装了一个隐蔽的探测器,探测器左右x米之内是探测范围。一... 查看详情
1289大鱼吃小鱼
模拟,在这里用栈模拟,一开始用了结构体数组从首尾两端分别遍历果断超时,复杂度n*n,用栈来模拟是线性复杂度。#include<iostream>#include<algorithm>#include<vector>#include<cstring>#include<cstdio>#include<queue>#includ... 查看详情
好多鱼--全国模拟
...数),牛牛现在想把新捕捉的鱼放入鱼缸。鱼缸内存在着大鱼吃小鱼的定律。经过观察,牛牛发现一条鱼A的大小为另外一条鱼B大小的2倍到10倍(包括2倍大小和10倍大小),鱼A会吃掉鱼B。考虑到这个,牛牛要放入的鱼就需要保证:1... 查看详情
51nod1289大鱼吃小鱼
#include<bits/stdc++.h>usingnamespacestd;constintmaxn=100100;inta[maxn],b[maxn];stack<int>s;intmain(){intn;cin>>n;for(inti=1;i<=n;i++)cin>>a[i]>>b[i];intans=0;for(inti 查看详情
51nod-1289大鱼吃小鱼
题目链接:1289 大鱼吃小鱼 思路:如果把向右的鱼丢进栈里。如果出现向左的鱼,那么让它跟栈里的鱼互吃。如果栈里的鱼都被它吃光,那么答案+1。最后答案加上栈里的鱼。1#include<bits/stdc++.h>2usingnamespacestd;34intmain()... 查看详情
51nod1289大鱼吃小鱼
Input示例54 03 12 01 05 0Output示例2 死者:213栈模拟把向右的鱼看成左括号进栈,向左的鱼看成右括号出栈。答案为没被吃掉的向左的鱼和最后剩在栈里的向右的鱼的个数之和。 #include<iostream>#... 查看详情
stl详解——stack和queue的模拟实现(代码片段)
文章目录容器适配器stack的模拟实现queue的模拟实现stack和queue的模拟实现都比较简单,所以这里就一起进行实现。容器适配器stack和queue有一点需要注意的是,虽然stack和queue中也可以存放元素,但在STL中并没有将其划... 查看详情
栈及其简单应用(代码片段)
...一句简单的话就可以完成栈的操作:top--;栈的实际操作与运用学习好栈并不只是学会简单的模拟和运用,还要更多地知道一道题为什么需要栈,需要栈来维护什么,这也是需要栈的原因.接下来会有一些实际的例题,可以更好地... 查看详情
stack,queue,priority_queue的模拟实现(代码片段)
stack,queue,priority_queue的模拟实现stack的模拟实现栈是一种先入后出的数据结构,主要具有以下接口上面就是stack(栈)的主要功能了,而这次我们要利用自己写的栈来实现这些结果在上面的例子中我们利用系统提供的stack实现... 查看详情
stack,queue,priority_queue的模拟实现(代码片段)
stack,queue,priority_queue的模拟实现stack的模拟实现栈是一种先入后出的数据结构,主要具有以下接口上面就是stack(栈)的主要功能了,而这次我们要利用自己写的栈来实现这些结果在上面的例子中我们利用系统提供的stack实现... 查看详情
c++从青铜到王者第十四篇:stl之stack类的初识和模拟实现(代码片段)
...言一、stack介绍和使用1.stack的介绍2.stack的使用二、stack的模拟实现总结前言一、stack介绍和使用1.stack的介绍stack文档的介绍翻译:stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容... 查看详情
[c++]stl_stack(栈)queue(队列)使用及其重要接口模拟实现
本篇博文主要介绍C++STL库中stack,queue的使用及其模拟实现,以及涉及到deque的介绍。1.stack1.1stack的介绍stack官方文档介绍1.stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进... 查看详情
c++stack与queue模拟实现(代码片段)
C++stack与queue模拟实现前言stack栈适配器stack的成员函数queue队列queue类总结前言xxxx无论是当初在学校最先学习C语言版的数据结构,还是现在学习STL,发现大家(包括我)都喜欢将stack(栈)和queue(... 查看详情
stack和queue使用及模拟实现(代码片段)
文章目录一.stack介绍二.stack使用三.stack模拟实现四.queue介绍五.queue使用六.queue模拟实现七.priority_queue的介绍仿函数八.priority_queue的使用九.priority_queue模拟实现(1).仿函数(2).push()(3).pop()(4).top()(5).empty()(6).size()(7).完整模拟实现一.stack... 查看详情