题解 SP212 【WATER - Water among Cubes】

· · 题解

虽然源OJ显示是bfs,可是我却觉得是堆。。。

思路:每次找到一个在最边上的最小的,然后把那个最小的删除,如果扫描周围的鸽子是否能装水(即这个格子低于边上的那个格子),如果可以蓄水,就加入到sum里。

记得删除完这个格子把与其相邻的格子也设为边上的格子哦,但需要注意的一点是如果这个格子可以蓄水,一定要赋成那个边上的格子,因为其他的格子不是只蓄水到这个格子的高度,而是可以到边上的那个格子。

但我们怎么求最小值呢?插入排序?但由于既要查找,又要插入每次的操作是O(log2(n)+n)太慢了。

块状链表?似乎快一点,每次可以接近O(2×\sqrt{n})可是还是慢了一点。

所以我们只能用堆来找最小值了,每次操作 O(log2(n)),总时间复杂度O(t×n×m×log2(n))。

最后,我们要避免元素在堆里面出现多次,如果已经在堆里,就要标记一下,只有当没被标记过的时候才可以插入。

代码

#include<bits/stdc++.h>
using namespace std;
struct xyq{
    int x,y,q; //q是元素的值(即装到多少高度就会溢出)
};
xyq tree[500005]; //堆。
bool mark[505][505]; //标记数组。
int size=0,a[505][505];
int gox[10]={0,0,1,-1}; //搜索方向(接着下面你也许就懂了)。
int goy[10]={1,-1,0,0};
void push(int a,int b,int c){ //插入一个节点的函数。
    size++;
    tree[size].q=a;
    tree[size].x=b;
    tree[size].y=c;
    int mq=size; //mq表示目前调整到的节点。
    while(tree[mq>>1].q>tree[mq].q){ //向上调整,(x>>1)是位运算,表示x/2。
        swap(tree[mq>>1],tree[mq]);
        mq>>=1;
    }
}
xyq pop(){
    xyq ret=tree[1];
    int t=2; //目前调整到的节点。
    tree[1]=tree[size--]; //删除不需要取消标记,因为删除了就不需要再插入。
    while(t<=size){ //向上调整。
        if(t<size&&tree[t].q>tree[t+1].q){
            t++;
        }
        if(tree[t].q<tree[t>>1].q){
            swap(tree[t],tree[t>>1]);
            t=(t<<1); //(x<<1)是位运算,表示2x。
        }else{
            break;
        }
    }
    return ret;
}
int main(){
    int i,j,n,m,nx,ny,k,t; //n,m是输入的行数和列数。nx,ny是搜索到的新节点
    long long sum=0;
    xyq zyl;
    cin>>t;
    for(int it=1;it<=t;it++){
    cin>>n>>m;
    for(i=0;i<=n;i++){
        for(j=0;j<=m;j++){
            mark[i][j]=0;
        }
    }
    sum=0; //清空所有使用记录。
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            cin>>a[i][j];
            if(i==0||i==n-1||j==0||j==m-1){
                push(a[i][j],i,j);
                mark[i][j]=1;
            }
        }
    }
    for(i=0;i<n*m;i++){
        zyl=pop();
        for(j=0;j<4;j++){ //对方向进行搜索
            nx=zyl.x+gox[j];
            ny=zyl.y+goy[j];
            if(nx>=0&&ny>=0&&nx<n&&ny<m&&!mark[nx][ny]){ //没超过边界并且没插入过。
                sum+=max(zyl.q-a[nx][ny],0);
                push(max(a[nx][ny],zyl.q),nx,ny);
                mark[nx][ny]=1; //标记。
            }
        }
    }
    cout<<sum<<endl;
    }
}