有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;
}