有N条鱼每条鱼的位置及大小均不同,他们沿着X轴游动,有的向左,有的向右。游动的速度是一样的,两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方向(0表示向左,1表示向右)。问足够长的时间之后,能剩下多少条鱼?Input第1行:1个数N,表示鱼的数量(1 <= N <= 100000)。
第2 - N + 1行:每行两个数Aii, Bii,中间用空格分隔,分别表示鱼的大小及游动的方向(1 <= Aii <= 10^9,Bii = 0 或 1,0表示向左,1表示向右)。Output输出1个数,表示最终剩下的鱼的数量。
Sample Input
5
4 0
3 1
2 0
1 0
5 0
Sample Output
2
网上搜到的比较清晰的思路
思路:模拟栈的操作,在栈为空的情况下,向左的鱼不做记录,向右的鱼记录,再次遇到向左的则吃,直到栈空或被吃。
为什么要记录向右的鱼?
分两种情况:
(1)记录向左的鱼,这时会发现,若之前的鱼向右而又没有记录,此时一个向左一个向右是相向而行的,不能进行比较,因此不能记录向左的鱼。
(2)记录向右的鱼,这时就算之前有相邻向左的鱼没有记录,由于一个向左一个向右相背而行也是不会相遇的,因此记录向右的鱼。
#include <cstdio>
#include <stack>
using namespace std;
int main()
{
stack<int> s; /*栈*/
int a[100000+5]; /*记录鱼的大小*/
int b[100000+5]; /*记录鱼的方向*/
int i, n, number; /*循环变量, 输入鱼的个数, 记录鱼数变化情况*/
scanf("%d", &n );
number = n;
for( i=0; i<n; i++ ){
scanf("%d%d", &a[i], &b[i] );
if( b[i] == 1 )
s.push( a[i] ); /*第一个鱼进栈*/
else{
while( s.size() ){
if( s.top() < a[i] ){ /*向左的鱼大于栈顶的鱼,则吃点栈顶鱼*/
s.pop();
number --;
}
else{
number --; /*向左的鱼小于栈顶的鱼,则被吃掉*/
break;
}
}
}
}
printf("%d\n", number ); /*输出最后剩余的鱼的个数*/
return 0;
}