蓝桥杯省模拟赛第十题(淹没城堡)
2023-02-18 16:42:44 时间
题目
有一片长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;
}
相关文章
- 行业方案 | 新规落地,企业集团财务公司如何构建数智财务体系?
- TAPD思享汇|高科制造企业如何软硬协同、敏捷提效?
- 瑞幸瞄准蜜雪冰城?
- 干货 | 深度学习在携程搜索词义解析中的应用
- 干货 | Islands Architecture(孤岛架构)在携程新版首页的实践
- 干货 | 提前在开发阶段暴露代码问题,携程Alchemy代码质量平台
- 干货 | 浅谈携程大住宿研发效能提升实践
- Adobe acrobat DC安装教程pdf编辑器全版本下载
- CAD 2020 软件安装教程CAD软件全版本下载
- AutoCAD2021软件安装步骤cad软件全版本下载
- cobrax 使用反射获取 flag 配置, 支持指针字段
- 万元的正版课程9.9元被盗卖
- ES6:模块化的基本语法
- 使用vite 快速创建项目
- producer参数---Kafka从入门到精通(七)
- react-react-dom v6 知识整合
- Kafka消息分区&producer拦截器&无消息丢失(八)
- React 18 componentDidMount重复执行两次的解决方案
- 消费者组consumer group详解-Kafka从入门到精通(九)
- KafkaConsumer-Kafka从入门到精通(十)