題干：

有N條魚每條魚的位置及大小均不同，他們沿著X軸游動，有的向左，有的向右。游動的速度是一樣的，兩條魚相遇大魚會吃掉小魚。從左到右給出每條魚的大小和游動的方向（0表示向左，1表示向右）。問足夠長的時間之后，能剩下多少條魚？Input第1行：1個數N，表示魚的數量(1 <= N <= 100000)。?
第2 - N + 1行：每行兩個數A ii, B ii，中間用空格分隔，分別表示魚的大小及游動的方向(1 <= A ii?<= 10^9，B ii?= 0 或 1，0表示向左，1表示向右）。Output輸出1個數，表示最終剩下的魚的數量。Sample Input 5 4 0 3 1 2 0 1 0 5 0Sample Output 2

解題報告：

????用棧直接模擬，十分簡單。向右游的就入棧，向左游的就依次判斷出棧與否。如果棧為空并且來了一條往左游的魚，那就ans++，最后ans+棧中元素的個數就是答案。

????本題亦可以直接模擬，但是較繁瑣，有空可以一試。

ac代碼：

#include<iostream> #include<cstdio> #include<stack>using namespace std; int main() {stack< int > s;int n,x,d,flag;int ans=0;int top=0;scanf("%d",&n);for(int i = 1; i<=n; i++) { // printf("\n****************************8\n") ;flag=0;scanf("%d%d",&x,&d);if(s.empty() && d==0) {ans++;}else if(s.empty()&&d==1) {s.push(x);}else if( !s.empty() && d==1 ) {s.push(x);}else {while(!s.empty()) {top=s.top();if(top>x) {flag=1;//表示向左游的這個魚被吃掉了（就是 這魚不夠大 不足以吃掉所有的魚）。 break; }else s.pop();}if(flag==0) ans++; } }printf("%d\n",s.size()+ans);return 0 ; }

總結

以上是生活随笔為你收集整理的【51nod-1289】大鱼吃小鱼的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。