EOJ----F. 蚂蚁

淩亂°似流年 2022-06-15 02:18 191阅读 0赞

## F. 蚂蚁 ##

**Time limit per test:** 0.5 seconds

**Time limit all tests:** 5.0 seconds

**Memory limit:** 256 megabytes

**Accept / Submit:** 23 / 64

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

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

![a-is-for-ant-9_coloring_page.b0942ffcae1870aed45b3509f6cdca49.png][]

### Input ###

第 1 行：一个整数 *N*![Image 1][]，表示蚂蚁的数量 (1≤*N*≤10![Image 1][]5![Image 1][])![Image 1][]。

第 2 到 *N*\+1![Image 1][] 行：每行两个数 *A*![Image 1][]*i*![Image 1][],*B*![Image 1][]*i*![Image 1][]![Image 1][] (1≤*A*![Image 1][]*i*![Image 1][]≤10![Image 1][]9![Image 1][]，*B*![Image 1][]*i*![Image 1][]∈\{ 0,1\})![Image 1][]，中间用空格分隔，分别表示蚂蚁的大小及爬  
行的方向，*B*![Image 1][]*i*![Image 1][]=0![Image 1][] 表示向左，*B*![Image 1][]*i*![Image 1][]=1![Image 1][] 表示向右。

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

### Output ###

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

### Examples ###

Input

5
    4 0
    3 1
    2 0
    1 0
    5 0

Output

错误代码：

//\#include<iostream>  
//\#include<cstdio>  
//\#include<algorithm>  
//\#include<cstring>  
//\#include<string>  
//using namespace std;  
//struct A  
//\{  
//    int a,b;  
//\} f\[100001\];  
//int main()  
//\{  
//    int n,ans;  
//    scanf("%d",&n);  
//    ans=0;  
//    for(int i=0; i<n; i++)  
//        scanf("%d %d",&f\[i\].a,&f\[i\].b);  
//    for(int i=0; i<n-1; i++)  
//    \{  
//        if(f\[i\].b==1&&f\[i+1\].b==0)  
//        \{  
//            if(f\[i\].a<=f\[i+1\].a)  
//            \{  
//                if(f\[i\].a<f\[i+1\].a)  
//                \{  
//                    ans++;  
//                    //i++;  
//                \}  
//                else  
//                    f\[i+1\]=f\[i\];  
//            \}  
//            else  
//            \{  
//                ans++;  
//                f\[i+1\]=f\[i\];  
//            \}  
//        \}  
//    \}  
//    printf("%d\\n",n-ans);  
//    return 0;  
//\}

AC的：

思路：用栈来模拟即可

#include <iostream>
    #include <stack>
    #define N 100005
    using namespace std;
    int main()
    {
        stack<int>s;
        int n,a,b,m;
        scanf("%d",&n);
        m=n;
        while(n--)
        {
            scanf("%d %d",&a,&b);
            if(b==1)
                s.push(a);
            if(b==0)
            {
                while(!s.empty())
                {
                    if(a>s.top())
                    {
                        s.pop();
                        m--;
                    }
                    else
                    {
                        m--;
                        break;
                    }
                }
            }
        }
        printf("%d\n",m);
        return 0;
    }

[Image 1]: 
[a-is-for-ant-9_coloring_page.b0942ffcae1870aed45b3509f6cdca49.png]: /images/20220615/257affc976ff4376aae73c234ebd0b54.png