蓝桥杯省模拟赛第十题(淹没城堡)

题目

有一片长n宽m的地方,上面有n个方块,该地图是立体的,所以方块可以叠加,地图数值代表在该坐标下有叠加的方块个数,现在有高h的水要淹没这片地方,请输出从水高度为1~h,被淹没的方块个数分别为多少。

样例输入

输入第一行为n和m,表示地图长和宽,然后是n行,每行m个数表示方块个数,最后一行输入一个h表示水的最高高度。
3 4
9 3 3 1
3 3 3 0
0 0 0 0
10

样例输出

7
13
19
20
21
22
23
24
25
25

数据范围

1<=n,m<=1000
1<=h<=100000
方块个数<1000000000

思路

虽然数据是二维的,但根据题意,即使把所有行连起来摆放也不影响,其次因为水的高度不算太高,数据不会太散,所以可以用桶排存储进一维数组,桶排不仅快(O(n))而且可以直接知道叠加高度为idx的方块列数有多少。

#define H 100005
long long tong[H] = {0};        
for(int i = 1;i <= n*m;i++){
    cin >> tmp;
    tmp = tmp>H?H:tmp;      //对于叠加高过最高水位的,直接让它高度=水位最高高度
    cin >> tong[i];
}

因为最高水位有十万,所以肯定要用到动规。申请一个数组hs,用于存储每一层淹没方块数量,从h层开始向下遍历,每一层淹没数量 = 叠加高度大于这一层的列数+叠加高度小于等于这一层的列数*该列方块数。

for(int i = h;i > 0;i--){
    hs[i] = tong[i]+fugai;
    fugai+=tong[i];
}

但每一层高度的方块,这一层能淹没,比他高的层数一定也能淹没,所以i+(h-i)层都需要加i层方块数量,但是如果用循环来加时间复杂度就为O(h^2),所以这个累加数据也要用动规,用一个数组leijia,存储比下标高的每层水位需要加的淹没方块数量。
那么最后从底向上来一遍leijia[i]+=leijia[i-1]即可。

完整代码

#include<iostream>
#include<cstdio>
#define H 100001

using namespace std;

int tong[100005];            //高度为下标的方块列数 
long long hs[100005];        //每层淹没数量 
long long leijia[100005];    //高度大于下标的水位额外淹没数量 
int fugai;                    //高度大于当前h的列数         
int main(){
    int n,m,h,tmp;
    cin >> n >> m;
    for(int i = 0;i < n*m;i++){
        cin >> tmp;
        if(tmp>H){
            tmp = H;
        }
        tong[tmp]++;
    }
    cin >> h;
    for(int i = h+1;i <= H;i++){
        fugai+=tong[i];
    }
    for(int i = h;i > 0;i--){
        hs[i] = tong[i]+fugai;
        leijia[i] = tong[i]+fugai;
        fugai+=tong[i];
    }
    for(int i = 1;i <= h;i++){
        leijia[i] += leijia[i-1];
        hs[i] += leijia[i-1];
        cout << hs[i]<< endl;
    }
    
    return 0;
}
本文作者:六月丶

本文链接:https://hctra.cn/index.php/archives/608/

版权声明:如无特别声明,本文即为六月'blog原创,仅代表个人观点,如要转载请务必注明文章出处。
最后修改:2020 年 05 月 01 日 10 : 24 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论