题目
有一片长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;
}