EOJ 3264 螞蟻（模拟+棧）

題目

http://acm.ecnu.edu.cn/problem/3264/

題意：水準線上有 N 隻螞蟻，每隻螞蟻的位置及大小均不同。他們沿着 X 軸爬行，有的向左，有的向右，爬行的速度是一樣的，兩隻螞蟻相遇大一點的會吃掉小的。

現在從左到右給出每隻螞蟻的大小和爬行的方向（0 表示向左，1 表示向右）。問足夠長的時間之後，能剩下多少隻螞蟻？

解題思路

比較簡單的模拟題。

注意到輸入是從左到右的，且螞蟻行走和互相吞噬模拟成入棧和出棧，是以用掃描每一個螞蟻，用棧模拟這些過程。

對于每個螞蟻 i，若棧頂螞蟻向右 且 螞蟻 i 向左，判斷兩者大小：

• 如果前者大，則 i 被吞噬，繼續處理下一個螞蟻；
• 如果 i 大，則前者被吞噬（出棧），用新的棧頂和 i 比較；
• 如果棧空了或者兩者方向相同，則 i 終于可以進棧了

注意棧空時入棧的兩個特殊情況：初始為空 和 新螞蟻吞噬棧頂後變空。

測試用例：

輸入

 
 
 
 
輸出：

           

AC代碼

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> P; //first為大小，second為方向
#define RIGHT 1
#define LEFT 0
const int maxn = +;

P ant[maxn];
stack<P> s;

int main()
{
    ios::sync_with_stdio(false);
    int n, sz, dir;
    cin >> n;
    for (int i = ; i < n; ++i)
        cin >> ant[i].first >> ant[i].second;
    while(!s.empty())
        s.pop();
    for (int i = ; i < n; ++i)
    {
        if(s.empty())
        {
            s.push(ant[i]);
            continue;
        }
        P tp = s.top();
        bool flag = true;
        while (tp.second == RIGHT && ant[i].second == LEFT)
        {
            if(ant[i].first < tp.first) //無法進棧
            {
                flag = false;
                break;
            }
            else if (ant[i].first > tp.first) //吃掉棧頂
            {
                s.pop();
                if(s.empty()) //棧已空
                    break;
                tp = s.top(); //新的棧頂繼續比較
            }
        }
        if(flag) //确定入棧
            s.push(ant[i]);
    }
    cout << s.size() << endl;
    return ;
}