CF371D Vessels 题解

· · 题解

谁说这道题要用链表做的！！！

警钟敲烂：

这道题一开始想用链表水过去，结果在外网 TLE 了 8 个点，所以，链表不是万能的！！！

大致思路：

本题考察的是并查集的活学活用，根据题目要求，我们可以想象一个事情：假如我现在在往第 k 个漏斗里注水，是不是就意味着我在向对大于等于 k 的没装满水的沙漏注水？因为我们可以知道，当一个沙漏被装满时，它的水就会流到大于它的编号的沙漏里面去，所以当我给 k 个沙漏装水时，我就已经给下面的沙漏准备好了水。

综上所述，如果第 k 个盘子注满水后，我们可以把 k 和 k + 1 个盘子合并起来，这样对 k 操作就是直接对大于等于 k 的盘子进行操作了。

最终，在计算答案时，我们只需要判断如果 \operatorname{find}(x) > n，则说明水已经溢出至地面，所有的沙漏均已装满。直接结束循环即可。

代码如下：

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
const int N = 2e5 + 50;
const int inf = 0x3f3f3f3f;
int a[N], fa[N], v[N];
int n, q;
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
    int t1 = find(x);
    int t2 = find(y);
    fa[t1] = t2;
}
void init()
{
    for (int i = 1; i <= n + 2; i++)
    {
        fa[i] = i;
    }
}
int main()
{
    n = read();
    init();
    for (int i = 1; i <= n; i++)
    {
        v[i] = read();
    }
    memset(a, 0, sizeof a);
    q = read();
    while (q--)
    {
        int op;
        op = read();
        if (op == 1)
        {
            int k, c;
            k = read();
            c = read();
            while (c)
            {
                k = find(k);
                if (k > n)
                {
                    break;
                }
                if (a[k] + c >= v[k])
                {
                    c -= (v[k] - a[k]);
                    a[k] = v[k];
                    merge(k, k + 1);
                }
                else
                {
                    a[k] += c;
                    c = 0;
                }
            }
        }
        else
        {
            int k;
            k = read();
            cout << a[k] << endl;
        }
    }
    return 0;
}

AC 记录