题目
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 ;
}