关键词：
收藏
关注
取消关注第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
用栈来存储b[i]=1的鱼（向右移动的，要去战斗的），当遇到b[i]=0的鱼（向左移动的，来挑战的），双方血拼，用ans记录牺牲的鱼。
最终剩下的鱼=n-ans;
1 #include <iostream> 2 #include <stack> 3 using namespace std; 4 int a[100005]; 5 int b[100005]; 6 stack<int> sta; 7 int main() 8 { 9 int n; 10 int ans=0; 11 cin>>n; 12 for(int i=0;i<n;i++) 13 { 14 cin>>a[i]; 15 cin>>b[i]; 16 } 17 for(int i=0;i<n;i++) 18 { 19 if(b[i]==0&&sta.empty()) 20 continue; 21 if(b[i]==1) 22 { 23 sta.push(a[i]); 24 continue; 25 } 26 while(!sta.empty()) 27 { 28 int tmp=sta.top(); 29 sta.pop(); 30 if(tmp>a[i]) 31 { 32 ans++; 33 sta.push(tmp); 34 break; 35 } 36 ans++; 37 } 38 } 39 cout<<n-ans<<endl; 40 return 0; 41 }
51nod1289大鱼吃小鱼
Input示例54 03 12 01 05 0Output示例2 死者：213栈模拟把向右的鱼看成左括号进栈，向左的鱼看成右括号出栈。答案为没被吃掉的向左的鱼和最后剩在栈里的向右的鱼的个数之和。 #include<iostream>#... 查看详情
51nod-1289大鱼吃小鱼
题目链接：1289 大鱼吃小鱼 思路：如果把向右的鱼丢进栈里。如果出现向左的鱼，那么让它跟栈里的鱼互吃。如果栈里的鱼都被它吃光，那么答案+1。最后答案加上栈里的鱼。1#include<bits/stdc++.h>2usingnamespacestd;34intmain()... 查看详情
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 查看详情
51nod1289stack
1289 大鱼吃小鱼题目来源： Codility基准时间限制：1 秒空间限制：131072 KB分值: 5 难度：1级算法题 收藏 关注有N条鱼每条鱼的位置及大小均不同，他们沿着X轴游动，有的向左，有的向右。游动的速度... 查看详情
大鱼吃小鱼（简单模拟）
题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1289从左往右将数字压入栈里（想象成一个水平向右的栈），如果鱼是向左的让它一直吃，直到被吃或者吃完为止importjava.util.Scanner;importjava.util.Stack;publicclassN1289{privatestaticScann... 查看详情
1289大鱼吃小鱼
模拟，在这里用栈模拟，一开始用了结构体数组从首尾两端分别遍历果断超时，复杂度n*n，用栈来模拟是线性复杂度。#include<iostream>#include<algorithm>#include<vector>#include<cstring>#include<cstdio>#include<queue>#includ... 查看详情
1289大鱼吃小鱼（栈）
1289 大鱼吃小鱼有N条鱼每条鱼的位置及大小均不同，他们沿着X轴游动，有的向左，有的向右。游动的速度是一样的，两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方向（0表示向左，1表示向右）。问足够... 查看详情
51nod1102面积最大的矩形（单调栈）
...明前面比它大的那些数最多只能延伸到它这里。自己手动模拟一下就可以了。1#inclu 查看详情
1289大鱼吃小鱼1305pairwisesumanddivide1344走格子1347旋转字符串1381硬币游戏
1289大鱼吃小鱼 有N条鱼每条鱼的位置及大小均不同，他们沿着X轴游动，有的向左，有的向右。游动的速度是一样的，两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方向（0表示向左，1表示向右）。问足够... 查看详情
1289大鱼吃小鱼（stl中栈的应用）(代码片段)
》》点击进入测试《《有N条鱼每条鱼的位置及大小均不同，他们沿着X轴游动，有的向左，有的向右。游动的速度是一样的，两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方向（0表示向左，1表示向右）。问... 查看详情
51nod1623完美消除（数位dp）
... 因为数的范围只有0~9，所以我们可以用一个二进制数来模拟这个栈，并塞到DP的状态里。 设$dp[i][j][k]$表示前i位数，已经进行了j次操作，栈的状态为k的方案数。 每次枚举一个数的时候，先把比这个数大的数在状态中都... 查看详情
51nod1437迈克步（单调栈）
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1437题意： 思路：单调栈题。求出以每个数为区间最大值的区间范围即可。1#include<iostream>2#include<algorithm>3#include<cstring>4#include<cstdio> 查看详情
51nod1102(单调栈/预处理)
题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1102 题意：中文题诶～ 思路：单调栈/预处理 （这篇博客就不细写了啦，只给出代码和转过来的两篇不错的题解，好困了～） 单调栈：http://blog.csdn.net/u012773... 查看详情
51nod1279单调栈
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=12791279扔盘子题目来源：Codility基准时间限制：1秒空间限制：131072KB分值:10难度：2级算法题收藏关注有一口井，井的高度为N，每隔1个单位它的宽度有变化。现在从井口往下面扔圆盘... 查看详情
51nod1952栈
1952 栈基准时间限制：1.5 秒空间限制：262144 KB分值: 80 难度：5级算法题LYK有一个栈，众所周知的是这个数据结构的特性是后进先出的。LYK感觉这样子不太美妙，于是它决定在这个前提下将其改进，也就是说，... 查看详情
51nod1215单调栈/迭代
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=12151215数组的宽度题目来源：Javaman基准时间限制：1秒空间限制：131072KB分值:80难度：5级算法题收藏关注N个整数组成的数组，定义子数组a[i]..a[j]的宽度为：max(a[i]..a[j])-min(a[i]..a[j])，... 查看详情
51nod1349最大值（单调栈）
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1349题意：求区间内最大值大于等于k的区间个数。 思路：利用求出对于以a[i]为最大值的区间范围，pre[i]表示左端范围，aft[i]表示右端范围，则区间个数为$(i-pre[i]+1)*(aft[i]-i+1)$。1... 查看详情
51nod1962区间计数（单调栈+二分）
维护两个单调递减的栈，当i加进栈，位置x的数弹出的时候，在另一个栈中找到和这个数一样大的数，计算贡献（x-靠右左端点）*（i-x）。#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<algorith... 查看详情