蓝桥杯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…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...

【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
webpack面试题
面试题:webpack介绍和简单使用 一、webpack(模块化打包工具)1. webpack是把项目当作一个整体,通过给定的一个主文件,webpack将从这个主文件开始找到你项目当中的所有依赖文件,使用loaders来处理它们&#x…...

路由基础-路由表
本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中,往往存在多个不同的IP网段,数据在不同的IP网段之间交互是需要借助三层设备的,这些设备具备路由能力,能够实现数据的跨网段转发。 路由是数据通信网络中最基…...

大模型——基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程
基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程 下载安装Docker Docker官网:https://www.docker.com/ 自定义Docker安装路径 Docker默认安装在C盘,大小大概2.9G,做这行最忌讳的就是安装软件全装C盘,所以我调整了下安装路径。 新建安装目录:E:\MyS…...