CCF认证-202403-04 | 十滴水

题目内容：

十滴水是一个非常经典的小游戏。

小 CC 正在玩一个一维版本的十滴水游戏。

我们通过一个例子描述游戏的基本规则。

游戏在一个 1×c1×c 的网格上进行，格子用整数 x(1≤x≤c)x(1≤x≤c) 编号，编号从左往右依次递增。

网格内 mm 个格子里有 1∼41∼4 滴水，其余格子里没有水。

在我们的例子中，c=m=5c=m=5，按照编号顺序，每个格子中分别有 2,4,4,4,22,4,4,4,2 滴水。

玩家可以进行若干次操作，每次操作中，玩家选择一个有水的格子，将格子的水滴数加一。

任何时刻若某个格子的水滴数大于等于 55，这个格子里的水滴就会向两侧爆开。

此时，这个格子的水被清空，同时对于左方、右方两个方向同时进行以下操作：找到当前格子在对应方向上最近的有水的格子，如果存在这样的格子，将这个格子的水滴数加一。

若在某个时刻，有多个格子的水滴数大于等于 55，则最靠左的先爆开。

在我们的例子中，若玩家对第三格进行操作，则其水滴数变为 55，故第三格水滴爆开，水被清空，其左侧最近的有水格子（第二格）和右侧最近的有水格子（第四格）的水量增加 11，此时每个格子中分别有 2,5,0,5,22,5,0,5,2 滴水。

此时第二格和第四格的水滴数均大于等于 55，按照规则，第二格的水先爆开，爆开后每个格子中分别有 3,0,0,6,23,0,0,6,2 滴水；最后第四格的水滴爆开，每个格子中分别有 4,0,0,0,34,0,0,0,3 滴水。

小 CC 开始了一局游戏并进行了 nn 次操作。

小 CC 在每次操作后，会等到所有水滴数大于等于 55 的格子里的水滴都爆开再进行下一次操作。

小 CC 想知道他的水平有多高，于是他想知道每一次操作后还有多少格子里有水。

保证这 nn 次操作都是合法的，即每次操作时操作的格子里都有水。

输入格式

输入的第一行三个整数 c,m,nc,m,n 分别表示网格宽度、有水的格子个数以及操作次数。

接下来 mm 行每行两个整数 x,wx,w，表示第 xx 格有 ww 滴水。

接下来 nn 行每行一个整数 pp，表示小 CC 对第 pp 格做了一次操作。

输出格式

输出 nn 行，每行一个整数表示这次操作之后网格上有水的格子数量。

数据范围

对于所有测试数据，

• 1≤c≤1091≤c≤109，1≤m≤min(c,3×105)1≤m≤min(c,3×105)，1≤n≤4m1≤n≤4m；
• 1≤x,p≤c1≤x,p≤c，1≤w≤41≤w≤4；
• 输入的所有 xx 两两不同；
• 对于每个输入的 pp，保证在对应操作时 pp 内有水。

特殊性质：在游戏的任意时刻（包括水滴爆开的连锁反应过程中），只有至多一个格子的水滴数大于等于 55。

输入样例：

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

输出样例：

2
1

题解：

         采用模拟求解，第一次尝试使用了结构体，新建了一个<int，int>的结构体water，然后将water压入vector，通过下标寻找水滴，然后递归求解。但是由于数据量实在太大，O（n）的搜索并不能承受住，就TLE了（并不是我不会map呜呜呜）。

        后来使用map与迭代器，递归进去首先新建迭代器it1和it2，分别对应在map中find的迭代器（即要操作的水滴）的前一个和后一个，要考虑当it是map的begin的情况。判断it1和it2的存在情况，并进行水滴数量的增加。从左边（即it1）开始递归（如果出现水量>=5的情况下），再对右边进行递归。

        注意：先左后右有可能导致原本要进行操作的右迭代器it2被提前爆炸（即erase）所以要在判断条件中加上 mp.find(it2->first) != mp.end() ，意为判断it2指向的map中的键值对是否还存在。

满分代码如下：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long int ll;

int c=0,m=0,n=0,i,j,k,num=0,t1=0,t2=0;

map<int ,int > mp;
map<int ,int>::iterator it;

void solution(map<int ,int >::iterator it){
    map<int,int>::iterator it1,it2;
    if(it==mp.begin()){
        it1=mp.end();
    }
    else{
        it--;
        it1=it;
        it++;
    }
    it++;
    it2=it;
    it--;
    mp.erase(it->first);
    if(it1!=mp.end()){
        it1->second++;
    }
    if(it2!=mp.end()){
        it2->second++;
    }
    if(it1!=mp.end() && it1->second >= 5){
        solution(it1);
    }
    if(it2!=mp.end() && mp.find(it2->first) != mp.end() && it2->second >= 5){
        solution(it2);
    }
    return;
}

main()
{
    cin >> c >> m >> n;
    for(i=0;i<m;i++){
        scanf("%d %d",&t1,&t2);
        mp[t1]=t2;
    }
    while(n>0){
        scanf("%d",&num);
        it=mp.find(num);
        it->second++;
        if(it->second>=5){
            solution(it);
        }
        printf("%d\n",mp.size());
        n--;
    }
}

55分超时代码如下（使用vector）： 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long int ll;

struct water{
    int n,w;
};

int cmd(water x,water y){
    return x.n<y.n;
}

int c=0,m=0,n=0,i,j,k,num=0;

vector<water> v;

water t;

bool check(water x){
    if(x.w>=5){
        //pq.push(x);
        return true;
    }
    return false;
}

void solution(int i){
    int t1=0,t2=0;
    if(i-1>=0){
        v[i-1].w++;
        if(v[i-1].w>=5){
            t1=1;
        }
    }
    if(i+1<v.size()){
        v[i+1].w++;
        if(v[i+1].w>=5){
            t2=1;
        }
    }
    v.erase(v.begin()+i);
    /*
    for(int j=0;j<v.size();j++){
        cout << v[j].n << " " << v[j].w << "\n";
    }
    cout << "------------" << "\n";
    */
    if(t1){
        //cout << "t1 in" << "\n";
        solution(i-1);
    }
    else if(t2){
        //cout << "t2 in" << "\n";
        solution(i);
    }
    return;
}

main()
{
    cin >> c >> m >> n;
    for(i=0;i<m;i++){
        //cin >> t.n >> t.w;
        scanf("%d %d",&t.n,&t.w);
        v.push_back(t);
    }
    sort(v.begin(),v.end(),cmd);
    while(n>0){
        //cin >> num;
        scanf("%d",&num);
        for(i=0;i<v.size();i++){
            if(v[i].n==num){
                v[i].w++;
                //cout << i << "\n";
                if(check(v[i])){
                    //cout << "in" << "\n";
                    solution(i);
                    break;
                }
            }
        }
        //cout << v.size() << "\n";
        printf("%d\n",v.size());
        n--;
    }
}