51nod 1289 大鱼吃小鱼 栈
2024-10-21 09:25:53
题目来源: Codility
基准时间限制:1 秒 空间限制:131072 KB
有N条鱼每条鱼的位置及大小均不同,他们沿着X轴游动,有的向左,有的向右。游动的速度是一样的,两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方向(0表示向左,1表示向右)。问足够长的时间之后,能剩下多少条鱼?
Input
第1行:1个数N,表示鱼的数量(1 <= N <= 100000)。
第2 - N + 1行:每行两个数A[i], B[i],中间用空格分隔,分别表示鱼的大小及游动的方向(1 <= A[i] <= 10^9,B[i] = 0 或 1,0表示向左,1表示向右)。
Output
输出1个数,表示最终剩下的鱼的数量。
Input示例
5
4 0
3 1
2 0
1 0
5 0
Output示例
2
思路:刚刚开始想还以为是贪心,发现有bug,就想是栈模拟;
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define esp 0.00000000001
#define pi 4*atan(1)
const int N=1e5+,M=1e6+,inf=1e9+,mod=1e9+;
int a[N];
stack<int>s;
int main()
{
int x,y,z,i,t;
int ans=;
scanf("%d",&x);
for(i=;i<x;i++)
{
scanf("%d%d",&a[i],&y);
if(y)
s.push(a[i]);
else
{
while(!s.empty())
{
if(a[i]>s.top())
{
ans++;
s.pop();
}
else
{
ans++;
break;
}
}
}
}
printf("%d\n",x-ans);
return ;
}
最新文章
- EventBus使用详解(一)——初步使用EventBus
- iOS 7.1 安装 企业应用 提示 无法下载应用程序
- paper 80 :目标检测的图像特征提取之(一)HOG特征
- lrzsz在CentOS7的安装
- CSS+DIV常用命名
- DataSnap如何监控Tcp/IP客户端的连接情况
- How do I create an installation log?
- SpringMVC框架学习笔记(3)——controller配置汇总
- ACM Misha and Changing Handles
- day42-python消息队列一
- Redis的KEYS命令引起宕机事件
- react使用ant-design组件库
- POJ2253(dijkstra堆优化)
- org.springframework.beans.factory.BeanCreationException,Invocation of init method failed,Context initialization failed
- Solr使用in语法查询
- C++笔记 2
- bzoj4353: Play with tree
- HTML 5+CSS 3网页设计经典范例 (李俊民,黄盛奎) 随书光盘​
- xampp开户,apache打开出现端口被占用提示
- springmvc----demo3---rest风格---bai
热门文章
- 2016-06-19 NOIP模拟赛
- JS实现当鼠标移动到图片上时,时图片旋转
- SpringBoot-------实现多数据源Demo
- Centos中查询目录中内容命名ls(六)
- win7安装laravel
- app开发需求文档怎么写
- Mybatis中insert返回主键ID
- 1.4 使用电脑测试MC20的接收英文短信功能
- 20160419 while练习,复习
- 异常:System.Runtime.InteropServices.Marshal.GetTypeFromCLSID(System.Guid)