PTA L2-045 堆宝塔

news/2024/6/24 7:49:01/文章来源:https://blog.csdn.net/m0_75081848/article/details/137293717

ta.jpg

堆宝塔游戏是让小朋友根据抓到的彩虹圈的直径大小,按照从大到小的顺序堆起宝塔。但彩虹圈不一定是按照直径的大小顺序抓到的。聪明宝宝采取的策略如下:

  • 首先准备两根柱子,一根 A 柱串宝塔,一根 B 柱用于临时叠放。
  • 把第 1 块彩虹圈作为第 1 座宝塔的基座,在 A 柱放好。
  • 将抓到的下一块彩虹圈 C 跟当前 A 柱宝塔最上面的彩虹圈比一下,如果比最上面的小,就直接放上去;否则把 C 跟 B 柱最上面的彩虹圈比一下:
    • 如果 B 柱是空的、或者 C 大,就在 B 柱上放好;
    • 否则把 A 柱上串好的宝塔取下来作为一件成品;然后把 B 柱上所有比 C 大的彩虹圈逐一取下放到 A 柱上,最后把 C 也放到 A 柱上。

重复此步骤,直到所有的彩虹圈都被抓完。最后 A 柱上剩下的宝塔作为一件成品,B 柱上剩下的彩虹圈被逐一取下,堆成另一座宝塔。问:宝宝一共堆出了几个宝塔?最高的宝塔有多少层?

输入格式:

输入第一行给出一个正整数 N(≤103),为彩虹圈的个数。第二行按照宝宝抓取的顺序给出 N 个不超过 100 的正整数,对应每个彩虹圈的直径。

输出格式:

在一行中输出宝宝堆出的宝塔个数,和最高的宝塔的层数。数字间以 1 个空格分隔,行首尾不得有多余空格。

输入样例:

11
10 8 9 5 12 11 4 3 1 9 15

输出样例:

4 5

样例解释:

宝宝堆成的宝塔顺次为:

  • 10、8、5
  • 12、11、4、3、1
  • 9
  • 15、9

做法:

1.拿一个彩虹圈t

        1.1.A可放,放A上

        1.2.B可放,放B上

        1.3.B不可放,完成一件宝塔制作,记录数量和最高高度,把B所有的大于t的放到A上,

         并把t放到A上,整理B。

代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1010;int B[N],A[N],id_a,id_b;int main()
{int n = 0,cnt = 0,h = 0;scanf("%d",&n);for(int i = 0;i < n;i++){int t = 0;scanf("%d",&t);if(!id_a || t < A[id_a - 1]) A[id_a++] = t;//A可放else{if(!id_b || B[id_b - 1] < t) B[id_b++] = t;//B可放else//完成一件宝塔制作{cnt++;h = max(h,id_a);//记录高度id_a = 0;for(int i = id_b - 1;i >= 0;i--)//B所有的大于t的放到A上if(B[i] > t) A[id_a++] = B[i],B[i] = 0;for(int i = 0;i < id_b;i++)//整理B的内部空间,把不为0的数往前放{if(B[i] == 0){int j = i + 1;while(j < id_b && !B[j])j++;if(j < id_b) B[i] = B[j],B[j] = 0;else{id_b = i;break;}}}A[id_a++] = t;//放t}}}if(id_a) cnt++,h = max(h,id_a);//处理剩余的if(id_b) cnt++,h = max(h,id_b);printf("%d %d",cnt,h);return 0;
}

结果: 

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

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

相关文章

MATLAB科研绘图与学术图表绘制从入门到精通

&#x1f482; 个人网站:【 摸鱼游戏】【神级代码资源网站】【工具大全】&#x1f91f; 一站式轻松构建小程序、Web网站、移动应用&#xff1a;&#x1f449;注册地址&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交…

Mybatis plue(二) 核心功能

核心功能 P5 条件构造器 mybatisplus支持各种复杂的where条件&#xff0c;可以满足日常开发的所有需求 wrapper就是条件构造器,wrapper就是顶层的&#xff0c; 示例&#xff1a; 查询出名字带0&#xff0c;存款大于等于1000的人的id,username,info,balance字段 Testvoid te…

Oracle Cloud公布 | 每小时 126 亿次 SQL 数据库查询

广而告之&#xff1a;2024 年数据技术嘉年华大会将于 4 月12-13 日在北京召开&#xff0c;春暖花开之际&#xff0c;数据库行业蓬勃发展之时&#xff0c;广邀天下豪杰&#xff0c;相聚北京&#xff0c;共论数据库技术发展的创新与未来。 注册&#xff1a;https://www.modb.pro/…

Adaboost集成学习 | Matlab实现基于GRU-Adaboost门控循环单元结合Adaboost集成学习时间序列预测(股票价格预测)

目录 效果一览基本介绍模型设计程序设计参考资料效果一览 基本介绍 Adaboost集成学习 | Matlab实现基于GRU-Adaboost门控循环单元结合Adaboost集成学习时间序列预测(股票价格预测) 模型设计 股票价格预测是一个具有挑战性的时间序列预测问题,可以使用深度学习模型如门控循环…

安卓Android 架构模式及UI布局设计

文章目录 一、Android UI 简介1.1 在手机UI设计中&#xff0c;坚持的原则是什么1.2 安卓中的架构模式1.2.1 MVC (Model-View-Controller)设计模式优缺点 1.2.2 MVP(Model-View-Presenter)设计模式MVP与MVC关系&#xff1a; 1.2.3 MVVM(Model—View—ViewModel ) 设计模式1.2.4 …

视觉里程计之对极几何

视觉里程计之对极几何 前言 上一个章节介绍了视觉里程计关于特征点的一些内容&#xff0c;相信大家对视觉里程计关于特征的描述已经有了一定的认识。本章节给大家介绍视觉里程计另外一个概念&#xff0c;对极几何。 对极几何 对极几何是立体视觉中的几何关系&#xff0c;描…

政务AI交互数字人推动政务“人工智能+”建设

传统的政务平台大多是单向与用户互动&#xff0c;缺乏即时反馈&#xff0c;导致用户需要花费大量时间理解信息&#xff0c;并难以提出问题得到及时解答。 AI交互数字人凭借其智能性&#xff0c;可以在政务网页、政务业务办理大厅一体机、政务APP/小程序等终端设备中&#xff0…

OSPF中配置静态路由实验简述

静态路由协议和OSPF&#xff08;开放最短路径优先&#xff09;协议是两种常见的路由协议&#xff0c;它们在路由选择和网络管理方面有一些区别。他们可以共存。 静态路由协议需要手动配置路由表&#xff0c;不会自动适应网络拓扑变化&#xff0c;适用于小型网络或者网络拓扑变化…

非关系型数据库(缓存数据库)redis的基础认知与安装

目录 一.关系型数据库和非关系型数据库 关系型数据库 非关系型数据库 关系数据库与非关系型数据库的区别 ①非关系数据 关系型数据库 非关系型数据库产生背景 数据存储流向 非关系型数据库 关系数据库 二.redis的简介 1.概念 2.Redis 具有以下几个优点: 3.Redi…

香港科技大学广州|数据科学与分析学域硕博招生宣讲会—天津大学专场

时间&#xff1a;2024年4月12日&#xff08;星期五&#xff09;14:00 地点&#xff1a;天津大学北洋园校区55楼B204 报名链接&#xff1a;https://www.wjx.top/vm/Q0cKTUI.aspx# 跨学科研究领域 *数据驱动的人工智能和机器学习 *统计学习和建模 工业和商业分析 *特定行业的数…

java 8 stream api将List<T>转换成树形结构

1、新建实体类 package com.example.springboot3.entity;import lombok.Builder; import lombok.Data;import java.util.List;Data Builder public class Menu {/*** id*/public Integer id;/*** 名称*/public String name;/*** 父id &#xff0c;根节点为0*/public Integer p…

Python深度学习034:cuda的环境如何配置

文章目录 1.安装nvidia cuda驱动CMD中看一下cuda版本:下载并安装cuda驱动2.创建虚拟环境并安装pytorch的torch_cuda3.测试附录1.安装nvidia cuda驱动 CMD中看一下cuda版本: 注意: 红框的cuda版本,是你的显卡能装的最高的cuda版本,所以可以选择低于它的版本。比如我的是11…

【2023】kafka入门学习与使用(kafka-2)

目录&#x1f4bb; 一、基本介绍1、产生背景2、 消息队列介绍2.1、消息队列的本质作用2.2、消息队列的使用场景2.3、消息队列的两种模式2.4、消息队列选型&#xff1a; 二、kafka组件1、核心组件概念2、架构3、基本使用3.1、消费消息3.2、单播和多播消息的实现 4、主题和分区4.…

AR智能眼镜解决方案_MTK平台安卓主板硬件芯片方案开发

AR智能眼镜&#xff0c;是一个可以让现场作业更智能的综合管控设备。采用移动互联网、大数据和云计算等技术&#xff0c;现场数据的采集与分析&#xff1b;同时实现前端现场作业和后端管理的实时连动、信息的同步传输与存储。让前端现场作业更加智能&#xff0c;后端管理更加高…

Java8 Stream API全面解析——高效流式编程的秘诀

文章目录 什么是 Stream Api?快速入门流的操作创建流中间操作filter 过滤map 数据转换flatMap 合并流distinct 去重sorted 排序limit 限流skip 跳过peek 操作 终结操作forEach 遍历forEachOrdered 有序遍历count 统计数量min 最小值max 最大值reduce 聚合collect 收集anyMatch…

6.8物联网RK3399项目开发实录-驱动开发之RTC实时时钟的使用(wulianjishu666)

90款行业常用传感器单片机程序及资料【stm32,stc89c52,arduino适用】 链接&#xff1a;https://pan.baidu.com/s/1M3u8lcznKuXfN8NRoLYtTA?pwdc53f RTC 使用 简介 AIO-3399J 开发板上有 一个集成于 RK808 上的RTC(Real Time Clock)&#xff0c;主要功能有时钟&#xff0c…

Linux-3 yum和vim

目录 本节目标&#xff1a; Linux 软件包管理器 yum 什么是软件包 1.yum是什么&#xff1f;软件包&#xff1f; 2.Linux(centos)的生态 3.yum的相关操作 我怎么知道我应该安装什么软件&#xff1f; 4.yum的本地配置 关于 rzsz 查看软件包 Linux编辑器-vim使用 1.v…

Red Hat配置本地yum源

Red Hat配置本地yum源 创建本地源文件夹 mkdir -p /mnt/cdrom挂载镜像文件至指定的目录 mount /dev/cdrom /mnt/cdrom备份本地源 cp -rf /etc/yum.repos.d /etc/yum.repos.d_$(date %Y%m%d_%H%M%S)删除默认原本地源 rm -rf /etc/yum.repos.d/*配置本地源&#xff0c;创建…

苹果应用上架攻略

苹果上架要求是苹果公司对于提交应用程序到苹果商店上架的要求和规定。这些要求主要是为了保证用户体验、应用程序的质量和安全性。以下是苹果上架要求的详细介绍&#xff1a;1. 应用程序的内容和功能必须符合苹果公司的规 苹果上架要求是苹果公司对于提交应用程序到苹果商店上…

Linux系统----------探索mysql数据库MHA高可用

目录 一、MHA概述 1.1 什么是 MHA 1.2MHA 的组成 1.2.1MHA Node&#xff08;数据节点&#xff09; 1.2.2MHA Manager&#xff08;管理节点&#xff09; 1.3MHA 的特点 1.4MHA工作原理 1.5数据同步的方式 1.5.1同步复制 1.5.2异步复制 1.5.3半同步复制 二、搭建 MySQ…