51Nod-1289 大鱼吃小鱼 题解

大鱼吃小鱼

题目概述

有N条鱼每条鱼的位置及大小均不同，他们沿着X轴游动，有的向左，有的向右。游动的速度是一样的，两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方向（0表示向左，1表示向右）。问足够长的时间之后，能剩下多少条鱼？

思路分析

用栈去维护向右移动的鱼

从左到右遍历，如果碰到向左的鱼，则判断鱼的大小与栈顶元素的关系，

如果栈顶的鱼更大，则忽略这条鱼（被栈顶吃掉），否则栈顶的鱼被吃掉退栈

一直到栈为空或者栈顶鱼大于这条向左的鱼

如果栈为空，则这条鱼活了下来，左边的其他鱼都被吃掉了

否则栈中剩余的鱼存活，这条向左的鱼被吃掉

最后记录向左移动存活的鱼（栈为空时计数）和向右移动存活的鱼（遍历到最后栈中剩下的鱼）

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long llong;
const int N = 2e5 + 5;
const int MOD = 1e9 + 7;
llong n;
int a[N], b[N];

int main() {
    #ifdef LOCAL
        freopen("D:/Code/ACM/in.in", "r", stdin);
        freopen("D:/Code/ACM/out.out", "w", stdout);
    #endif
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    int ans = 0;
    stack<int> st;
    for (int i = 0; i < n; i++) {
        if (b[i]) {
            st.push(i);
        } else {
            while (st.size() && a[i] > a[st.top()]) {
                st.pop();
            }
            if (st.empty()) {
                ans++;
            }
        }
    }
    ans += st.size();
    cout << ans << "\n";
    return 0;
}