题目描述

样例输入

5 5 2
1 2
2 4
3 4
4 4
5 2
3
1

样例输出

2
1

解

离散化和双向链表(存储前驱和后继)
每次会找一个有水的格子，将水滴数加一,所以要操作的坐标肯定在这m个坐标之中，将这m个格子的坐标映射到1~m, 题目中说“表示第x格有w滴水”,所以就不用去重了。题目中还说“给出的是第x格的水滴数”，所以要保序，排序还是要的。
虽然在我们自己在模拟的时候，会出现没有水滴的格子夹在有水的格子之间，但是无论是选定格子加一的操作还是水滴爆开后的操作，都与其无关，即我们可以忽略这些没有水滴的格子，只将有水滴的格子联系起来,构成双向链表，这样爆开后影响左右最近的有水的格子就转换为影响前驱和后继格子。

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;
const int N = 3e5 + 5;
vector<int> alls;
vector<PII> add;
bool vis[N];
int n, m, c;

struct node{
    int w;
    int l, r;
}a[N]; 

int find(int x){
    int l = 0, r = alls.size() - 1;
    while(l < r){
        int mid = l + r >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l + 1;
}

int main(){
    scanf("%d%d%d", &c, &m, &n);
    for(int i = 0; i < m; ++i){
        int x, w; scanf("%d%d", &x, &w);
        add.push_back({x, w}); 
        alls.push_back(x); //格子的坐标 
    }
    sort(alls.begin(), alls.end());

    for(int i = 0; i < m; ++i){
        int x = find(add[i].x); //通过格子坐标得到对应坐标的值x 
        int y = add[i].y;
        a[x].w = y; 
        a[x].l = x - 1; //前驱坐标的值 
        a[x].r = x + 1; //后继坐标的值 
    }

    priority_queue<int, vector<int>, greater<int>> q;
    int res = m; //一开始肯定是有m个格子有水 
    for(int i = 0; i < n; ++i){
        int p; scanf("%d", &p);
        int pos = find(p);
        a[pos].w ++;
        if(a[pos].w >= 5){
            q.push(pos);
        }
        while(q.size()){
            auto t = q.top();
            q.pop();
//          for(int i = 1; i <= c; ++i){
//              cout << a[i].w << ' ';
//          }
//          puts("");
            res --; //进了堆的都是要爆成0的 
            a[t].w = 0;
            int l = a[t].l, r = a[t].r;
            a[l].r = r; //让当前节点的前一个和后一个相连，因为当前的已经爆完了 
            a[r].l = l;
            if(l > 0){ //这里就不用判断是否存在水滴了，因为能连上的肯定是有的 
                a[l].w ++;
                if(a[l].w >= 5 && !vis[l]){ //引入vis，防止一个点多次入堆 
                    q.push(l);
                    vis[l] = true;
                }
            }
            if(r <= m && a[r].w > 0){
                a[r].w ++;
                if(a[r].w >= 5 && !vis[r]){
                    q.push(r);
                    vis[r] = true;
                }
            }           
        }
        cout << res << '\n';
    }
    return 0;
}

代码二

#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;


map<int, int> idx;
const int N = 3e5 +5;
bool vis[N];
int c, m, n;

struct node{
    int x, w;
    int l, r;
    bool operator < (const node &M) const{
        return x < M.x;
    }
}a[N];


int main(){
    scanf("%d%d%d", &c, &m, &n);    
    for(int i = 1; i <= m; ++i){
        scanf("%d%d", &a[i].x, &a[i].w);
    }
    sort(a + 1, a + 1 + m);
    for(int i = 1; i <= m; ++i){
        idx[a[i].x] = i;
        a[i].l = i - 1;
        a[i].r = i + 1;
    }

    priority_queue<int, vector<int>, greater<int>> q;
    int res = m;
    for(int i = 0; i < n; ++i){
        int p; scanf("%d", &p);
        int pos = idx[p];
        a[pos].w ++;
        if(a[pos].w >= 5){
            q.push(pos);
        }
        while(q.size()){
            auto t = q.top();
            q.pop();
//          for(int j = 1; j <= c; ++j) cout << a[j].w <<' ';
//          puts("");
            res --;
            int l = a[t].l, r = a[t].r;
            a[l].r = r;
            a[r].l = l;
            if(l > 0){
                a[l].w ++;
                if(a[l].w >= 5 && !vis[l]) {
                    q.push(l);
                    vis[l] = true;
                }
            }
            if(r <= m){
                a[r].w ++;
                if(a[r].w >= 5 && !vis[r]){
                    q.push(r);
                    vis[r] = true;
                }
            }
        }
        cout << res << '\n';
    }
    return 0;
} 

参考

https://blog.csdn.net/whaoe_m/article/details/138682452
https://zhuanlan.zhihu.com/p/695717149
本人水平有限，如有纰漏，敬请指正，欢迎讨论