17.看楼房

目录

Description

Input

Output

Notes

思路

注意事项

C++完整代码(含详细注释)


Description

小张在暑假时间进行了暑期社会调查。调查的内容是楼房的颜色如何影响人们的心情。于是他找到了一个楼房从左到右排成一排的小区,这个小区一共有

n

栋楼房,每个楼房有一个颜色

c_i

和一个高度

h_i

。小张调查的内容为每次他站在第

i

栋楼和第

i+1

栋楼之间向左看,他记录下此时他看到的楼房颜色数作为他的调查结果。

由于小张在暑假时间沉迷游戏来不及做实地调查,只好拜托你将调查结果告诉他。

Input

本题有多组数据。

每组数据第一行一个整数

n

。表示有

n

栋楼房从左到右排成一排。

第二行

n

个数,表示每个楼房的颜色

(1 \leq c_i \leq 10^6 )

第三行

n

个数,表示每个楼房的高度

(1 \leq c_i \leq 10^9 )

数据保证所有组数据的

\sum{n} \leq 1000000

Output

每组数据输出

n

个数,第

i

个数表示他站在第

i

栋楼和第

i+1

栋楼之间向左看,能够看到的楼房颜色数。

Notes

在从左向右看楼房的时候,左边较矮的楼房会被右边较高的楼房挡住。


思路

使用两个栈,分别存储楼房的颜色和高度。

遍历楼房时,如果新入栈的楼房高度小于栈顶的楼房高度,则将新入栈的楼房的颜色和高度分别压入颜色栈和高度栈,并更新能够看到的楼房颜色数。

如果新入栈的楼房高度大于等于栈顶的楼房高度,则依次弹出栈顶的楼房,直到栈顶的楼房高度大于新入栈的楼房高度。

在每次弹出楼房时,如果弹出的是最后一个该颜色的楼房,则更新能够看到的楼房颜色数。最后,输出当前能够看到的楼房颜色数。


注意事项

  1. 代码中使用了两个栈来存储楼房的颜色和高度,确保栈顶元素始终是当前能够看到的最高楼房。
  2. 使用一个数组 c_class 来记录每种颜色的楼房数量,方便判断是否是新的颜色。
  3. 在每次入栈和出栈时,都需要更新 c_class 数组和 c_num 变量,以保证能够正确计算能够看到的楼房颜色数。
  4. 注意处理输入输出,使用 scanf 和 printf 来提高输入输出效率。
  5. 注意处理每组数据之间的换行符。

 

C++完整代码(含详细注释)

#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
using namespace std;int main() {int num;cin >> num; // 读入数据组数stack<int> stack_c, stack_h; // 用两个栈分别存储楼房的颜色和高度while (num--) { // 循环处理每组数据int n;cin >> n; // 读入楼房的数量stack_c = stack<int>(); // 清空颜色栈stack_h = stack<int>(); // 清空高度栈vector<long long> c_class(1000000, 0); // 用于记录每种颜色的楼房数量vector<long long> c(n,0), h(n,0); // 分别存储楼房的颜色和高度long long c_num = 0; // 记录能够看到的楼房颜色数// 输入楼房颜色for (int i = 0; i < n; i++) {scanf("%lld", &c[i]);}// 输入楼房高度for (int i = 0; i < n; i++) {scanf("%lld", &h[i]);}// 遍历楼房for (int i = 0; i < n; i++) {if (stack_h.empty() || h[i] < stack_h.top()) { // 如果栈顶为空或者新入栈元素小于栈顶stack_h.push(h[i]);stack_c.push(c[i]);if (++c_class[c[i]] == 1) c_num++; // 如果是新的颜色,则更新c_num}else if (stack_h.top() <= h[i]) { // 如果新入栈元素大于等于栈顶while (!stack_h.empty() && stack_h.top() <= h[i]) { // 依次弹出栈顶元素,直到栈顶元素大于新入栈元素if (--c_class[stack_c.top()] == 0) c_num--; // 如果弹出的是最后一个该颜色的楼房,则更新c_numstack_h.pop();stack_c.pop();}stack_h.push(h[i]);stack_c.push(c[i]);if (++c_class[c[i]] == 1) c_num++; // 如果是新的颜色,则更新c_num}printf("%lld%c", c_num, i == n - 1 ? '\n' : ' '); // 输出当前能够看到的楼房颜色数}}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/117122.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

51单片机项目(7)——基于51单片机的温湿度测量仿真

本次做的设计&#xff0c;是利用DHT11传感器&#xff0c;测量环境的温度以及湿度&#xff0c;同时具备温度报警的功能&#xff1a;利用两个按键&#xff0c;设置温度阈值的加和减&#xff0c;当所测温度大于温度阈值的时候&#xff0c;蜂鸣器就会响起&#xff0c;进行报警提示。…

安卓 tcp 客户端

安卓 tcp 客户端 Server:8888 是Qt 写的Tcp 服务器 ip 是 192.168.2.103 port是8888 安卓手机运行 kotlin 语法的Tcp Client &#xff0c;连接&#xff0c;收发数据 效果如下图 Tcpclient package com.example.myapplicationimport android.os.Handler import android.os.Loo…

【leetcode 力扣刷题】数学题之计算次幂//次方:快速幂

利用乘法求解次幂问题—快速幂 50. Pow(x, n)372. 超级次方 50. Pow(x, n) 题目链接&#xff1a;50. Pow(x, n) 题目内容&#xff1a; 题目就是要求我们去实现计算x的n次方的功能函数&#xff0c;类似c的power()函数。但是我们不能使用power()函数直接得到答案&#xff0c;那…

ARM Cortex-M 的 SP

文章目录 1、栈2、栈操作3、Cortex-M中的栈4、MDK中的SP操作流程5、Micro-Lib的SP差别1. 使用 Micro-Lib2. 未使用 Micro-Lib 在嵌入式开发中&#xff0c;堆栈是一个很基础&#xff0c;同时也是非常重要的名词&#xff0c;堆栈可分为堆 (Heap) 和栈 (Stack) 。 栈(Stack): 一种…

EG1164大功率同步整流升压模块开源,最高效率97%

EG1164大功率同步整流Boost升压电源模块&#xff0c;最高效率97%&#xff0c;输入电压8~50V&#xff0c;输出电压8~60V可调&#xff0c;最大功率300瓦以上&#xff0c;开关频率219kHz。 白嫖了张嘉立创的彩色丝印券就随便画了个板试试&#xff0c;第一次打彩色丝印。 因为我测…

flutter plugins插件【一】【FlutterJsonBeanFactory】

1、FlutterJsonBeanFactory 在Setting->Tools->FlutterJsonBeanFactory里边自定义实体类的后缀&#xff0c;默认是entity 复制json到粘贴板&#xff0c;右键自己要存放实体的目录&#xff0c;可以看到JsonToDartBeanAction Class Name是实体名字&#xff0c;会默认加上…

基于硬件隔离增强risc-v调试安全1_问题描述

安全之安全(security)博客目录导读 2023 RISC-V中国峰会 安全相关议题汇总 说明&#xff1a;本文参考RISC-V 2023中国峰会如下议题&#xff0c;版权归原作者所有。

每日一题 2511. 最多可以摧毁的敌人城堡数目

难度&#xff1a;简单 翻译&#xff1a;寻找距离最远的 1 和 -1 的组合&#xff0c;要求它们之间只有0 class Solution:def captureForts(self, forts: List[int]) -> int:res, t 0, -1for i, fort in enumerate(forts):if fort -1 or fort 1:if t > 0 and fort ! f…

前端Vue自定义得分构成水平柱形图组件 可用于系统专业门类得分评估分析

引入Vue自定义得分构成水平柱形图组件&#xff1a;cc-horBarChart 随着技术的发展&#xff0c;传统的开发方式使得系统的复杂度越来越高&#xff0c;一个小小的改动或小功能的增加可能会导致整体逻辑的修改&#xff0c;造成牵一发而动全身的情况。为了解决这个问题&#xff0c…

扫盲:常用NoSQL数据库

前言 关系型数据库产品很多&#xff0c;如 MySQL、Oracle、Microsoft SQL Sever 等&#xff0c;但它们的基本模型都是关系型数据模型。 非关系型数据库又称为&#xff1a;NoSQL &#xff0c;没有统一的模型&#xff0c;而且是非关系型的。 常见的 NoSQL 数据库包括键值数据库、…

【前端】Vue2 脚手架模块化开发 -快速入门

&#x1f384;欢迎来到边境矢梦的csdn博文&#x1f384; &#x1f384;本文主要梳理Vue2 脚手架模块化开发 &#x1f384; &#x1f308;我是边境矢梦&#xff0c;一个正在为秋招和算法竞赛做准备的学生&#x1f308; &#x1f386;喜欢的朋友可以关注一下&#x1faf0;&#x…

【MATLAB第70期】基于MATLAB的LightGbm(LGBM)梯度增强决策树多输入单输出回归预测及多分类预测模型(全网首发)

【MATLAB第70期】基于MATLAB的LightGbm(LGBM)梯度增强决策树多输入单输出回归预测及多分类预测模型&#xff08;全网首发&#xff09; 一、学习资料 (LGBM)是一种基于梯度增强决策树(GBDT)算法。 本次研究三个内容&#xff0c;分别是回归预测&#xff0c;二分类预测和多分类预…

系列五、Java操作RocketMQ简单消息之同步消息

一、概述 同步消息的特征是消息发出后会有一个返回值&#xff0c;即RocketMQ服务器收到消息后的一个确认&#xff0c;这种方式非常安全&#xff0c;但是性能上却没有那么高&#xff0c;而且在集群模式下&#xff0c;也是要等到所有的从机都复制了消息以后才会返回&#xff0c;适…

Linux系统Ubuntu以非root用户身份操作Docker的方法

本文介绍在Linux操作系统Ubuntu版本中&#xff0c;通过配置&#xff0c;实现以非root用户身份&#xff0c;进行Docker各项操作的具体方法。 在文章Linux系统Ubuntu配置Docker详细流程&#xff08;https://blog.csdn.net/zhebushibiaoshifu/article/details/132612560&#xff0…

如何使用Puppeteer进行新闻网站数据抓取和聚合

导语 Puppeteer是一个基于Node.js的库&#xff0c;它提供了一个高级的API来控制Chrome或Chromium浏览器。通过Puppeteer&#xff0c;我们可以实现各种自动化任务&#xff0c;如网页截图、PDF生成、表单填写、网络监控等。本文将介绍如何使用Puppeteer进行新闻网站数据抓取和聚…

mac idea启动没反应 无法启动

遇到的问题如下&#xff1a; 启动idea&#xff0c;没反应 无法启动&#xff0c;不论破解还是别的原因&#xff0c;总之无法启动了 应用程序–找到idea–右击显示包内容–Contents–MacOS–打开idea 弹出框提示如下&#xff1a; 双击这个idea可执行文件 1&#xff09;先查看日志…

JS中的new操作符

文章目录 JS中的new操作符一、什么是new&#xff1f;二、new经历了什么过程&#xff1f;三、new的过程分析四、总结 JS中的new操作符 参考&#xff1a;https://www.cnblogs.com/buildnewhomeland/p/12797537.html 一、什么是new&#xff1f; 在JS中&#xff0c;new的作用是通过…

【OpenCV入门】第七部分——图像的几何变换

文章结构 缩放dsize参数实现缩放fx参数和fy参数实现缩放 翻转仿射变换平移旋转倾斜 透视cmath模块 缩放 通过resize()方法可以随意更改图像的大小比例&#xff1a; dst cv2.resize(src, dsize, fx, fy, interpolation)src&#xff1a; 原始图像dsize&#xff1a; 输出图像的…

链表OJ练习(2)

一、分割链表 题目介绍&#xff1a; 思路&#xff1a;创建两个链表&#xff0c;ghead尾插大于x的节点&#xff0c;lhead尾插小于x的节点。先遍历链表。最后将ghead尾插到lhead后面&#xff0c;将大小链表链接。 我们需要在创建两个链表指针&#xff0c;指向两个链表的头节点&…

深入了解Docker镜像操作

Docker是一种流行的容器化平台&#xff0c;它允许开发者将应用程序及其依赖项打包成容器&#xff0c;以便在不同环境中轻松部署和运行。在Docker中&#xff0c;镜像是构建容器的基础&#xff0c;有些家人们可能在服务器上对docker镜像的操作命令不是很熟悉&#xff0c;本文将深…