首先感谢 guoliu 佬的点拨

题目

CCF 十滴水

思路

首先分析题目，这里让我们在一维数组内实现十滴水游戏。考虑到一次操作可能会引发多次反应，容易想到使用队列存储待引发的反应

因为这里一位棋盘的范围给的非常大，无法直接使用数组模拟表示，考虑使用离散化或者unordered_map进行映射(写题解的时候想到直接离散化或许能更简洁的解决问题，奈何本人对离散化不熟，这里只写 map 的思路)

使用 unordered_map 维护格子编号与水滴数的映射关系，这样我们只需要将待处理的格子编号推入队列即可轻松维护待处理队列

这个思路的难点有两个：

• 如何查找当前格子左右两侧最近的有水滴的格子编号
• 如何在多个格子同时满足反应条件时使最靠左的的格子优先反应

第一点

如果使用离散化的话似乎可以很简单的维护这段关系，下标移动一下就好了

然而 unordered_map 并没有下标这个概念，这个容器的底层是红黑树，本质上维护的是格子编号与水滴数的哈希关系

考虑将有水滴的格子单独列成一个线性表进行维护，由于其有序性，并且考虑到我们需要对内容进行查找，使用set容器较为合适，在最后统计结果的时候也更加方便

set<int> ind;                // 存储有水的格子的编号

 ind.erase(u);
                auto it = ind.lower_bound(u);  // 查找左右相邻的格子
                auto iter = it;
                if (it != ind.begin()) {
                    it--;
                    q.push(*it);
                }
                if (iter != ind.end())
                    q.push(*iter);

以上，已经可以拿到 45 分了

第二点

这个点我一开始死活想不出来，后来经过大佬的点拨才想起了优先队列这个东西
详细了解这玩意请移步[算法]priority_queue

简单来说，这个队列从使用上来说更像栈，将元素推入队列后，会自动将最值送至队首，正好符合我们先处理最左边格子反应的需求

tips

还有一点容易忽略，较早发生的连锁反应可能将之后进行操作的点水滴清零，所以要带上一个判断

if (ma[u] == 0)
                // 可能有无水滴格子加入队列的情况
                // 因为左侧先进行操作 可能有后进入队列的点中水滴已经消失
                continue;

实现

#include <algorithm>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define int long long
using namespace std;

int c, m, n;
unordered_map<int, int> ma;  // 棋盘
set<int> ind;                // 存储有水的格子的编号

int ans = 0;
priority_queue<int, vector<int>, greater<int>> q;
// 优先队列，自动将较小的元素放至队首

signed main() {
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> c >> m >> n;

    for (int i = 1; i <= m; i++) {
        int x, w;
        cin >> x >> w;
        ma[x] = w;  // x格有w滴水
        ind.insert(x);
    }

    // 有积累的多任务处理，容易想到使用队列存放待处理事项

    for (int i = 1; i <= n; i++) {
        int p;
        cin >> p;
        q.push(p);
        while (!q.empty()) {
            int u = q.top();  // u是当前水滴的格数
            q.pop();

            if (ma[u] == 0)
                // 可能有无水滴格子加入队列的情况
                // 因为左侧先进行操作 可能有后进入队列的点中水滴已经消失
                continue;

            ma[u]++;
            if (ma[u] >= 5) {
                // 此时第u格中的水大于5
                // 应将u左边和右边的各自依次加入队列
                // 难点在于如何设计查找两边的格子
                // 一直当前点为第u格，要找到u格是第几滴水
                ma[u] = 0;
                ind.erase(u);
                auto it = ind.lower_bound(u);  // 查找左右相邻的格子
                auto iter = it;
                if (it != ind.begin()) {
                    it--;
                    q.push(*it);
                }
                if (iter != ind.end())
                    q.push(*iter);
            }
        }

        // 统计有水的格子的数量 遍历ma
        ans = ind.size();
        cout << ans << '\n';
    }

    return 0;
}