【简单模拟】ABC240 D - Strange Balls

浅浅的花香味﹌ 2024-03-23 11:23 50阅读 0赞

**虽然是简单模拟，但是不妨碍我不会**

[D - Strange Balls (atcoder.jp)][D - Strange Balls _atcoder.jp]

题意：

![012422e6724d480baee3a027f8764531.png][]

思路：

在模拟的时候，先去明确要维护的是什么东西，然后再去考虑修改操作对要维护的东西的影响，再去添加需要维护的量

答案是每次操作之后栈里剩余多少球

那么考虑每次操作

如果进球之后不消，那么cnt++，栈里加球即可

但是如果消掉之后，栈里一个个球出来复杂度会很高

因此考虑不进重复的球，然后维护每个球的出现次数

如果消掉了，只pop一次即可

Code：

#include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int Inf=1e18;
    
    stack<pair<int,int> > S;
    int n;
    int a[mxn];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(S.empty()){
                S.push({a[i],1});
                cnt++;
            }else if(S.top().first==a[i]){
                S.top().second++;
                cnt++;
                if(S.top().second==a[i]){
                    cnt-=a[i];
                    S.pop();
                }
            }else{
                S.push({a[i],1});
                cnt++;
            }
            cout<<cnt<<'\n';
        }
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[D - Strange Balls _atcoder.jp]: https://atcoder.jp/contests/abc240/tasks/abc240_d
[012422e6724d480baee3a027f8764531.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/9df38e1061784aad91629e3b8ff53ccc.png