题解 CF821C 【Okabe and Boxes】

先上正解(?

#include<bits/stdc++.h>
using namespace std;
int a[3000005],n,m=0,l,ans;
char s[100];
bool cmp(int a,int s)
{
    return a>s;
}
int main()
{
    cin>>l;
    int i=1;
    m=0;
    while(i<=l)
    {
        scanf("%s",s);
        if(s[0]=='a')
        {
            cin>>a[++m];
        }
        else
        {
            if(a[m]!=i)
            {
                ans++;
                sort(a+1,a+m+1,cmp);
            }
            a[m--]=0;
            i++;
        }
    }
    cout<<ans;
}

如果你提交了它，那么恭喜你，它

所以我们要稍稍优化亿下：

先上代码

正解

#include<bits/stdc++.h>
using namespace std;
int a[3000005],n,m=0,l,ans,AC=0;
char s[100];
int main()
{
    cin>>l;
    int i=1;
    m=0;
    while(i<=l)
    {
        scanf("%s",s);
        if(s[0]=='a')
        {
            cin>>a[++m];
        }
        else
        {
            if(m)
            {
                if(a[m]!=i)
                {
                    ans++;
                    m=0;
                }
                else a[m--]=0;
            }
            i++;
        }
    }
    cout<<ans;
    return AC;
}

原理

我们可以不将栈排序，直接将栈清空即可，

为什么呢？

因为使用魔法——排序后

我们排完之后不放回栈里面去。

因为已经在外面排好序了

2021.1.2.16:54