AtCoder Beginner Contest 240 D

Created on June 08, 2023

2023   ·   data structures   contest

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;
}