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個の数を出力し、最終的に残った魚の数を表します.
サンプル入力
サンプル出力
ぶんせき
スタックの使用
C++プログラム
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;
}