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