acwing_5722_十滴水

下面这篇大佬的题解属实是把指针用明白了，可以好好理解一下：

原题解连接：AcWing 5722. 一个简单模拟实现 - AcWing

map/unordered_map的用法:见收藏夹

#include<iostream>
#include<unordered_map>
#include<map>

using namespace std;

//有水的格子
struct Gz {
    int drop;  //水的数量
    Gz *left;  //左边的有水的格子
    Gz *right; //右边的有水的格子
};

int main() {
    int c, m, n;
    cin >> c >> m >> n;
    unordered_map<int, Gz *> mp;    //用来查找每次操作对应编号p的格子的指针
    Gz *l = nullptr;
    int msize = m;                 //目前有水格子数
    int x, w, p;

    //不用unordered_map的原因，给输入的m排序，以使left和right有意义(在csp网站提交的时候一个没过，找了半天才发现m是可以乱序的...)
    map<int, int> mmp;//为什么这里不用数组呢？
    //我的看法是有水的格子相对于所有的格子来说很少，如果将所有的格子都遍历一遍，那么时间复杂度将是不可接受的。

    for (int i = 0; i < m; ++i) {
        cin >> x >> w;
        mmp[x] = w;
    }

    //对着输入存信息
    for (auto i = mmp.begin(); i != mmp.end(); ++i) {
        if (i == mmp.begin()) {
            Gz *t = new Gz;
            mp[i->first] = t;
            t->drop = i->second;
            t->left = l;
            t->right = nullptr;
            l = t;
        } else {
            Gz *t = new Gz;
            mp[i->first] = t;
            t->drop = i->second;
            t->left = l;
            t->right = nullptr;
            l->right = t; //如果格子不是第一个有水的格子，需要多做一步处理
            l = t;
        }
    }

    //对每次操作进行模拟
    for (int i = 0; i < n; ++i) {
        cin >> p;
        Gz *t = mp[p];
        t->drop++;

        //未到4则直接返回目前有水格子数
        if (t->drop <= 4) {
            cout << msize << endl;
        } else {
            while (t) {
                //如果左节点存在则更新左节点
                if (t->left) {
                    t->left->drop++;
                    t->left->right = t->right;
                }
                //如果右节点存在则更新右节点
                if (t->right) {
                    t->right->drop++;
                    t->right->left = t->left;
                }
                msize--;    //删除当前格子

                //如果左节点超过了4，则先跳转到左节点执行操作
                if (t->left && t->left->drop > 4) {
                    t = t->left;
                }
                    //左节点无需操作再检查右结点
                else if (t->right && t->right->drop > 4) {
                    // 注意这里为什么要用else if
                    t = t->right;
                } else {
                    break;
                }
            }
            cout << msize << endl;
        }
    }

    return 0;
}