当前位置：首页 > news >正文

acwing_5722_十滴水

news 2025/7/2 11:38:19

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 ift = t->right;} else {break;}}cout << msize << endl;}}return 0;
}