51Nod_1289大魚は小魚を食べる【桟】

1268 ワード

51Nod_1289大きな魚は小さな魚を食べます
                                    http://www.51nod.com/Challenge/Problem.html#!#problemId=1289
 
 
タイトル
N匹の魚はそれぞれ位置や大きさが異なり、X軸に沿って泳いでいたり、左に向かったり、右に向かったりしています.泳ぐスピードは同じで、2匹の魚が出会った大きな魚は小さな魚を食べます.各魚の大きさと泳ぐ方向を左から右に与える(0は左、1は右).十分な時間を聞いてから、魚は何匹残っていますか.
入力
1行目:1個数N、魚の数を表す(1) <= N <= 100000).2番目 - N + 1行:1行あたり2個の数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

ぶんせき
スタックの使用
C++プログラム
#include
#include 

using namespace std;

stacks;//s        

int main()
{
	int n,x,d,count=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x,&d);
		if(s.empty()&&d==0)//       ,        ,           
			count++;
		else if(d==1)//              
			s.push(x); 
		else{//              ,            
		  while(!s.empty()){
			if(s.top()>x)
				break;
			else
				s.pop();
			}
		  if(s.empty())//                 ,           
		    count++;
		}
	}
	printf("%d
",count+s.size()); return 0; }