Codeforces Round #218 (Div. 2)?D:http://codeforces.com/problemset/problem/371/D

題意：就是有一些盤子，盤子里可以裝水，這些盤子是從上到下一次排開的，然后會有一些操作1,p ,x，表示在第p個盤子里加入水x，如果這個盤子裝不下，水就會流向下一個盤子。2 p，表示查詢第p個盤子里有多少水。

題解：這一題用到并查集是真的沒有想到，也很難想到。水向下流的過程，就相當于兒子找父親的過程，然后用并查集直接模擬出來，就可以了。具體可以看看代碼。一開始，往線段樹和樹狀數組上想，總是想不到解決辦法。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=2e5+10; 7 int f[N],val[N],a[N]; 8 int n,m,t1,t2,t3; 9 void init(){ 10 memset(val,0,sizeof(val)); 11 memset(a,0,sizeof(a)); 12 for(int i=1;i<=n;i++) 13 f[i]=i; 14 } 15 int Find(int x){ 16 int s; 17 for(s=x;s!=f[s];s=f[s]); 18 while(s!=x){ 19 int temp=f[x]; 20 f[x]=s; 21 x=temp; 22 } 23 return s; 24 } 25 int main(){ 26 while(~scanf("%d",&n)){ 27 init(); 28 for(int i=1;i<=n;i++){ 29 scanf("%d",&val[i]); 30 a[i]=val[i]; 31 } 32 scanf("%d",&m); 33 for(int i=1;i<=m;i++){ 34 scanf("%d%d",&t1,&t2); 35 if(t1==1){ 36 scanf("%d",&t3); 37 int r=Find(t2); 38 while(t3>0){ 39 if(val[r]>=t3){ 40 val[r]-=t3; 41 break; 42 } 43 else{ 44 t3-=val[r]; 45 val[r]=0; 46 int temp=r++; 47 if(r>n)break; 48 else r=Find(r); 49 f[temp]=r; 50 } 51 } 52 } 53 else 54 printf("%d\n",a[t2]-val[t2]); 55 } 56 } 57 } View Code

?

轉載于:https://www.cnblogs.com/chujian123/p/3895034.html

總結

以上是生活随笔為你收集整理的Vessels的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。