Codeforces Round #218 (Div. 2) D. Vessels(思维 并查集)

时间:2022-12-22 08:38:49

题意:从上到下有n个杯子,编号从1到n。每个杯子有一定体积v[i]. 两种操作:1 x y, 向x水杯倒y水; 2 x, 询问x水杯有多少水. (水杯水溢出会往下流)

n,q <= 2e5

思路:暴力倒水的话是n*q,很多次要经过满的水杯,很费时,可以用并查集维护每个水杯往下的第一个非满的水杯。


代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e6+5;
int a[maxn], cur[maxn], pre[maxn];

int Find(int x)
{
int r = x;
while(pre[r] != r) r = pre[r];
int i = x, j;
while(pre[i] != r)
{
j = pre[i];
pre[i] = r;
i = j;
}
return r;
}

void join(int x, int y)
{
int a = Find(x);
int b = Find(y);
if(a > b)
pre[b] = a;
else
pre[a] = b;
}

int main(void)
{
int n;
while(cin >> n)
{
memset(cur, 0, sizeof(cur));
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]), pre[i] = i;
pre[n+1] = n+1;
int q;
scanf("%d", &q);
while(q--)
{
int cmd, x, y;
scanf("%d%d", &cmd, &x);
if(cmd == 1)
{
scanf("%d", &y);
while(y)
{
int t = Find(x);
if(t == n+1) break;
if(a[t]-cur[t] >= y)
{
cur[t] += y;
y = 0;
}
else
{
y -= a[t]-cur[t];
cur[t] = a[t];
join(t, t+1);
}
x = t;
}
}
else printf("%d\n", cur[x]);
}
}
return 0;
}