题解 P1486 【[NOI2004]郁闷的出纳员】

1517460958dyc · 2019-01-13 12:06:13 · 题解

STL vector 牛逼！

根据 @qwqqqq dalao的思路，水了一波vector（同时感谢 @落叶知秋声 dalao带我入vector平衡树的坑），再加了个delta，优化后不用卡常了！（用的时间大约是 @qwqqqq dalao的三分之一）

蒟蒻的Accepted

qwqqqq大佬

#include<cstdio>
#include<vector>
using namespace std;
int n,minw,delta=0;
vector<int> a;
inline int read()
{
    int x=0;
    char c=getchar();
    while (c<'0'||c>'9')
        c=getchar();
    while (c>='0'&&c<='9')
        x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x;
}
int main()
{
    n=read();minw=read();
    int cur=0,left=0,k;
    char code;
    while (n--)
    {
        code=getchar();
        while (code<'A'||code>'Z')
            code=getchar();
        k=read();
        switch (code)
        {
            case 'I':
            {
                if (k>=minw)
                {
                    ++cur;
                    a.insert(lower_bound(a.begin(),a.end(),k-delta),k-delta);
                }
                break;
            }
            case 'A':
            {
                delta+=k;
                break;
            }
            case 'S':
            {
                delta-=k;
                a.erase(a.begin(),lower_bound(a.begin(),a.end(),minw-delta));
                left+=(cur-a.size());
                cur=a.size();
                break;
            }
            case 'F':
            {
                printf("%d\n",(k>cur)?-1:(a[cur-k]+delta));
                break;
            }
        }
    }
    printf("%d",left);
    return 0;
}