YACS 2023年8月月赛 乙组 T3 香槟塔 题解

题目链接

乙组中比较好的一道思维题。

首先考虑暴力，如果没满就倒满了就往下继续倒，直到倒完或溢出为止，但如果开始就全满然后每次都从最上面倒那么 $O(n^2)$ 就超时了。

我们希望找到一个数据结构（当然不是也行）能够快速得到从某个位置向下（包括当前位置）第一个没满的香槟塔，显然并查集。

初始时每个点指向自己，如果它满了就指向下一个，每个杯子只会满一次，所以时间复杂度为 $O(n)$。

代码：

#include<iostream>
using namespace std;
int n,q,x,y;
int w[100005],f[100005],fa[100005];
char c;
int find(int x){
    if(fa[x]==x)return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        fa[i]=i;
    }
    fa[n+1]=n+1;
    cin>>q;
    while(q--){
        cin>>c>>x;
        if(c=='A'){
            cin>>y;
            while(x!=n+1&&f[x]+y>w[x]){
                y-=w[x]-f[x];
                f[x]=w[x];
                fa[x]=x+1;
                int fx=find(x);
                x=fx;
            }
            f[x]+=y;
        }else cout<<f[x]<<"\n";
    }
    return 0;
}