题目：

F. 蚂蚁

Time limit per test: 0.5 seconds

Time limit all tests: 5.0 seconds

Memory limit: 256 megabytes

Accept / Submit: 112 / 336

水平线上有 N 只蚂蚁，每只蚂蚁的位置及大小均不同。他们沿着 X 轴爬行，有的向左，有的向右，爬行的速度是一样的，两只蚂蚁相遇大一点的会吃掉小的。

现在从左到右给出每只蚂蚁的大小和爬行的方向（0 表示向左，1 表示向右）。问足够长的时间之后，能剩下多少只蚂蚁？

Input

第 1 行：一个整数 N，表示蚂蚁的数量 (1≤N≤105)。

第 2 到 N+1 行：每行两个数 Ai,Bi (1≤Ai≤109，Bi∈{0,1})，中间用空格分隔，分别表示蚂蚁的大小及爬
行的方向，Bi=0 表示向左，Bi=1 表示向右。

对于 3/8 的数据，存在 x 满足：所有坐标比 x 小的蚂蚁向左爬、坐标比 x 大的蚂蚁向右爬；或者所有坐标比 x 小的蚂蚁向右爬、坐标比 x 大的蚂蚁向左爬。

Output

输出最终剩下的蚂蚁的数量。

Examples

input

output

题解：

　　可以通过简单的栈模拟，对于向左走的蚂蚁如果没有向右走的蚂蚁直接加入进栈，如果有，则比较大小，向左的蚂蚁大吃掉向右走的蚂蚁（pop），否则是被吃掉。

　　对于向右走的直接加入栈中。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <string>
 7 #include <vector>
 8 #include <map>
 9 #include <set>
10 #include <stack>
11 #include <queue>
12 #include <sstream>
13 #include <algorithm>
14 using namespace std;
15 #define pb push_back
16 #define mp make_pair
17 #define ms(a, b)  memset((a), (b), sizeof(a))
18 #define eps 0.0000001
19 typedef long long LL;
20 typedef unsigned long long ULL;
21 const int inf = 0x3f3f3f3f;
22 const LL INF = 0x7fffffff;
23 const int maxn = 1e5+10;
24 const int mod = 1e9+7;
25 int a[maxn];
26 int b[maxn];
27 void init() {
28 
29 }
30 void solve() {
31     int n, k, ans = 0;
32     scanf("%d", &n);
33     stack<int>s0;
34     stack<int>s1;
35     for(int i = 1;i<=n;i++){
36         scanf("%d%d", &a[i], &b[i]);
37         if(b[i] == 0){
38             while(!s1.empty()&&a[i] > s1.top()){
39                 s1.pop();
40             }
41             if(s1.empty()){
42                 s0.push(a[i]);
43             }
44         }
45         else{
46             s1.push(a[i]);
47         }
48     }
49     printf("%d
", s0.size()+s1.size());
50 }
51 int main() {
52 #ifdef LOCAL
53     freopen("input.txt", "r", stdin);
54 //      freopen("output.txt", "w", stdout);
55 #endif // LOCAL
56 
57     solve();
58 
59     return 0;
60 }

View Code

你努力的时候，比你厉害的人也在努力。