526互联

AtCoder Beginner Contest 240 D

发布时间 2023-06-08 19:31:40作者: magicat

D - Strange Balls

tag：栈模拟

发现自己隔了快半年再做此题看错相同数字的球消失的条件，不是 \(k \geq 2\) 而是 \(k = a_i\) 电子竞技不需要视力

题意：当球 \(a_i (1 \leq i \leq N)\) 有 \(a_i\) 个一起出现时，这 \(a_i\) 个球就会消失，问每次放一个球进去，放进去后还剩多少个球？

用个栈记录下当前球的编号和个数即可

放球按一下操作

graph LR 放球 --> 栈空 栈空 --> 添加新的元素到栈顶 放球 --> 栈不空 栈不空 --> 栈顶元素等于要放进去球的编号 栈不空 --> 栈顶元素不等于要放进去球的编号 栈顶元素等于要放进去球的编号 --> 栈顶球的编号等于栈顶球的数量 栈顶球的编号等于栈顶球的数量 --> 出栈 栈顶元素不等于要放进去球的编号 --> 添加新的元素到栈顶

更多细节见代码：

int hh, tt, a[N];
array<int, 2> stk[N];

void solve()
{   
    hh = 1, tt = 0;
    int n;  cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    int res = 0;
    for(int i = 1; i <= n; i++)
    {
        res++;
        if(tt < hh)
            stk[++tt] = {a[i], 1};
        else
        {
            if(tt >= hh && a[i] == stk[tt][0])
            {
                stk[tt][1]++;
                if(tt >= hh && stk[tt][0] == stk[tt][1])
                    res -= stk[tt][1], tt--;
            }
            else
                stk[++tt] = {a[i], 1};
        }
        cout<<res<<'\n';
    }
    return;
}