蓝桥杯2117砍竹子(简单易懂 包看包会版)
问题描述
这天, 小明在砍竹子, 他面前有 n 棵竹子排成一排, 一开始第 i 棵竹子的 高度为 hi.
他觉得一棵一棵砍太慢了, 决定使用魔法来砍竹子。魔法可以对连续的一 段相同高度的竹子使用, 假设这一段竹子的高度为 H, 那么
用一次魔法可以 把这一段竹子的高度都变为 ⌊H2⌋+1⌋, 其中 ⌊x⌋ 表示对 x 向下取整。小明想 知道他最少使用多少次魔法可
让所有的竹子的高度都变为 1 。
输入格式
第一行为一个正整数 n, 表示竹子的棵数。
第二行共 n 个空格分开的正整数 hi, 表示每棵竹子的高度。
输出格式
一个整数表示答案。
样例输入
6
2 1 4 2 6 7
样例输出
5
样例说明
其中一种方案:
214262: 214267→214262→214222→211222→111222→111111 共需要 5 步完成
评测用例规模与约定
对于 20% 的数据, 保证 n≤1000,hi≤106 。 对于 100%的数据, 保证 n≤2×105,hi≤1018 。
运行限制
- 最大运行时间:2s
- 最大运行内存: 256M
解题思路
这是一道不需要思考思维 要求实现细节的贪心思维题目
首先 易得一个贪心策略:优先砍所剩竹子中高度最大的竹子 砍完高度高的竹子后由于高度变低,所以可能会跟原来高度低的竹子一块被砍 所以策略后半部分为 尽可能制造出多的高度相同的连续竹子 然后一起砍
实现细节:会卡sqrt的精度 只能过65%的数据
每次利用堆取出 并记录下最高竹子的长度和编号 之后利用长度相同 编号相邻的竹子一起砍一次的策略 只砍一次 依次入堆
AC代码展示
如果觉得有用 就点赞+收藏 关注一下吧
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<LL,int> PLI;
const int N=2e5+10;
int n;
LL x,res;
priority_queue<PLI> q;void solve(){while(!q.empty()){PLI t=q.top(); q.pop();LL t1=t.first; int t2=t.second;LL high=sqrtl(t1/2+1); //砍竹子//注意:此题会卡sqrt的精度 要用sqrtl 返回long doubleif(high!=1) q.push({high,t2});//其实也可以理解为 对连续且长度相同的树的一列 就一起砍了 减少次数while(!q.empty()&&q.top().first==t1&&q.top().second==t2-1){t2--;q.pop();if(high!=1) q.push({high,t2}); //注意 放的时候 竹子的高度是砍过的 }res++; //出现高度不同或编号不连续 即不能连续砍时 就++一次 每次取出一颗树 最后就会砍一次 只不过贪心一下是否可以一次多砍几棵树 }
}int main(){IOS;cin>>n;for(int i=0;i<n;i++){cin>>x;if(x!=1) q.push({x,i});} solve();cout<<res<<endl; return 0;
}
相关文章:
蓝桥杯2117砍竹子(简单易懂 包看包会版)
问题描述 这天, 小明在砍竹子, 他面前有 n 棵竹子排成一排, 一开始第 i 棵竹子的 高度为 hi. 他觉得一棵一棵砍太慢了, 决定使用魔法来砍竹子。魔法可以对连续的一 段相同高度的竹子使用, 假设这一段竹子的高度为 H, 那么 用一次魔法可以 把这一段竹子的高度都变为 ⌊H2⌋…...

LCD与lvgl
LCD与lvgl 目录 LCD与lvgl 回顾 LCD 的驱动层讲解 1、LCD 的常见接口 2、我们的 LCD 的参数 3、LCD 的设备树说明 4、LCD 的设备树说明 5、如何移植 LCD 的驱动(重点) LCD 的应用层开发 1:LCD 应用开发->界面开发的方法 2:LVGL 模拟器安装 3:LVGL 工程创建和…...

SpringBoot 赋能:精铸超稳会员制医疗预约系统,夯实就医数据根基
1绪论 1.1开发背景 传统的管理方式都在使用手工记录的方式进行记录,这种方式耗时,而且对于信息量比较大的情况想要快速查找某一信息非常慢,对于会员制医疗预约服务信息的统计获取比较繁琐,随着网络技术的发展,采用电脑…...

android studio 读写文件操作(应用场景二)
android studio版本:2023.3.1 patch2 例程:readtextviewIDsaveandread 本例程是个过渡例程,如果单是实现下图的目的有更简单的方法,但这个方法是下一步工作的基础,所以一定要做。 例程功能:将两个textvi…...

小尺寸低功耗蓝牙模块在光伏清扫机器人上的应用
一、引言 随着可再生能源的迅速发展,光伏发电系统的清洁与维护变得越来越重要。光伏清扫机器人通过自动化技术提高了清洁效率,而蓝牙模组的集成为这些设备提供了更为智能的管理和控制方案。 二、蓝牙模组的功能与实现: 蓝牙模组ANS-BT103M…...

防火墙有什么作用
防火墙的作用:1. 提供网络安全防护;2. 实施访问控制和流量过滤;3. 检测和阻止恶意攻击;4. 保护内部网络免受未经授权的访问;5. 监控网络流量和安全事件;6. 支持虚拟专用网络(VPN)。防…...

MongoDB-BSON 协议与类型
前言: MongoDB 是一个高性能、无模式的 NoSQL 数据库,广泛应用于大数据处理和实时数据存储。作为一个数据库系统,MongoDB 的核心之一就是其使用的 BSON(Binary JSON)格式,它用于存储数据以及在客户端和数据…...

学习threejs,使用VideoTexture实现视频Video更新纹理
👨⚕️ 主页: gis分享者 👨⚕️ 感谢各位大佬 点赞👍 收藏⭐ 留言📝 加关注✅! 👨⚕️ 收录于专栏:threejs gis工程师 文章目录 一、🍀前言1.1 ☘️VideoTexture 视频纹理 二、…...
怎么获取键值对的键的数值?
问: 通过paelData.cardMap.C0002112可以获取到Cooo2112里面的数据,但是有时候接口返回的不是C0002112而是C0002093或者其他值,请问我该怎么写? 后端返回的数据是这样的: cardMap: { C0002112: { name: Item 1, va…...

数据结构排序算法详解
数据结构排序算法详解 1、冒泡排序(Bubble Sort)2、选择排序(Selection Sort)2、插入排序(Insertion Sort) 1、冒泡排序(Bubble Sort) 原理:越小的元素会慢慢“浮”到数…...
在Linux设置postgresql开机自启动,创建一个文件 postgresql-15.service
在Linux设置postgresql开机自启动,创建一个文件 postgresql-15.service 在Linux设置postgresql开机自启动,创建一个文件 postgresql-15.service1. 创建 systemd 服务文件2. 编辑服务文件3. 保存并退出4. 重新加载 systemd 配置5. 启动 PostgreSQL 服务6.…...
【kafka】消息队列的认识,Kafka与RabbitMQ的简单对比
什么是消息队列? 消息队列(Message Queue,简称 MQ)是一个在不同应用程序、系统或服务之间传递数据的机制。 它允许系统间异步地交换信息,而无需直接交互,确保消息的可靠传输。 想象一下,你正在…...

ProjectSend 身份认证绕过漏洞复现(CVE-2024-11680)
0x01 产品描述: ProjectSend 是一个开源文件共享网络应用程序,旨在促进服务器管理员和客户端之间的安全、私密文件传输。它是一款相当流行的应用程序,被更喜欢自托管解决方案而不是 Google Drive 和 Dropbox 等第三方服务的组织使用。0x02 漏洞描述: ProjectSend r1720 之前…...

Android笔记(三十四):onCreate执行Handler.post在onResume后才能执行?
背景 偶然发现一个点,就是在onCreate执行Handler.post在onResume后才执行,以下是测试代码 多次运行的结果一致,为什么execute runnable不是在onCreate和onResume之间执行的呢,带着疑问撸了一遍Activity启动流程 关键源码分析 …...
关闭模组的IP过滤功能
关闭模组的IP过滤功能 关闭模组的IP过滤功能 本脚本用于关闭模组的IP过滤功能,关闭后, 源地址不是终端IP的数据包,也可以被模组转发给网络 关闭模组的IP过滤功能 cat > /usr/bin/ipfilter << "EOF"echo -e "ATCFUN…...

算法分析与设计复习笔记
插入排序 1. void insert_sort(int A[ ],int n) 2. { 3. int a,i,j; 4. for (i1;i<n;i) { 5. a A[ i ]; 6. j i – 1; 7. while (j>0 && A[j]>a) { 8. A[ j…...
vue-amap 高德地图
vue-amap是一套基于Vue 2/vue3和高德地图的地图组件 vue-amap 高德地图2.0版本的对应vue3...

Numpy基础练习
import numpy as np 1.创建一个长度为10的一维全为0的ndarray对象,然后让第5个元素等于1 n np.zeros(10,dtypenp.int32) n[4] 12.创建一个元素从10到49的ndarray对象 n np.arrange(10,50)3.将第2题的所有元素位置反转 n[::-1]使用np.random.random创建一个10*10的ndarray对象…...

一番赏小程序定制开发,打造全新抽赏体验平台
随着盲盒的热潮来袭,作为传统的潮玩方式一番赏也再次受到了大家的关注,市场热度不断上升! 一番赏能够让玩家百分百中奖,商品种类丰富、收藏价值高,拥有各种IP,从而吸引着各个圈子的粉丝玩家,用…...
【前端】将vue的方法挂载到window上供全局使用,也方便跟原生js做交互
【前端】将vue的方法挂载到window上供全局使用,也方便跟原生js做交互 <template><div><el-button click"start">调用方法</el-button></div> </template> <script> // import { JScallbackProc } from ./JScal…...

汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...

C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
在 Spring Boot 项目里,MYSQL中json类型字段使用
前言: 因为程序特殊需求导致,需要mysql数据库存储json类型数据,因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”
非常好,我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题,统一使用 二重复合函数: z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y)) 来全面说明。我们会展示其全微分形式(偏导…...