当前位置: 首页 > news >正文

蓝桥杯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开发背景 传统的管理方式都在使用手工记录的方式进行记录&#xff0c;这种方式耗时&#xff0c;而且对于信息量比较大的情况想要快速查找某一信息非常慢&#xff0c;对于会员制医疗预约服务信息的统计获取比较繁琐&#xff0c;随着网络技术的发展&#xff0c;采用电脑…...

android studio 读写文件操作(应用场景二)

android studio版本&#xff1a;2023.3.1 patch2 例程&#xff1a;readtextviewIDsaveandread 本例程是个过渡例程&#xff0c;如果单是实现下图的目的有更简单的方法&#xff0c;但这个方法是下一步工作的基础&#xff0c;所以一定要做。 例程功能&#xff1a;将两个textvi…...

小尺寸低功耗蓝牙模块在光伏清扫机器人上的应用

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

防火墙有什么作用

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

MongoDB-BSON 协议与类型

前言&#xff1a; MongoDB 是一个高性能、无模式的 NoSQL 数据库&#xff0c;广泛应用于大数据处理和实时数据存储。作为一个数据库系统&#xff0c;MongoDB 的核心之一就是其使用的 BSON&#xff08;Binary JSON&#xff09;格式&#xff0c;它用于存储数据以及在客户端和数据…...

学习threejs,使用VideoTexture实现视频Video更新纹理

&#x1f468;‍⚕️ 主页&#xff1a; gis分享者 &#x1f468;‍⚕️ 感谢各位大佬 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍⚕️ 收录于专栏&#xff1a;threejs gis工程师 文章目录 一、&#x1f340;前言1.1 ☘️VideoTexture 视频纹理 二、…...

怎么获取键值对的键的数值?

问&#xff1a; 通过paelData.cardMap.C0002112可以获取到Cooo2112里面的数据&#xff0c;但是有时候接口返回的不是C0002112而是C0002093或者其他值&#xff0c;请问我该怎么写&#xff1f; 后端返回的数据是这样的&#xff1a; cardMap: { C0002112: { name: Item 1, va…...

数据结构排序算法详解

数据结构排序算法详解 1、冒泡排序&#xff08;Bubble Sort&#xff09;2、选择排序&#xff08;Selection Sort&#xff09;2、插入排序&#xff08;Insertion Sort&#xff09; 1、冒泡排序&#xff08;Bubble Sort&#xff09; 原理&#xff1a;越小的元素会慢慢“浮”到数…...

在Linux设置postgresql开机自启动,创建一个文件 postgresql-15.service

在Linux设置postgresql开机自启动&#xff0c;创建一个文件 postgresql-15.service 在Linux设置postgresql开机自启动&#xff0c;创建一个文件 postgresql-15.service1. 创建 systemd 服务文件2. 编辑服务文件3. 保存并退出4. 重新加载 systemd 配置5. 启动 PostgreSQL 服务6.…...

【kafka】消息队列的认识,Kafka与RabbitMQ的简单对比

什么是消息队列&#xff1f; 消息队列&#xff08;Message Queue&#xff0c;简称 MQ&#xff09;是一个在不同应用程序、系统或服务之间传递数据的机制。 它允许系统间异步地交换信息&#xff0c;而无需直接交互&#xff0c;确保消息的可靠传输。 想象一下&#xff0c;你正在…...

ProjectSend 身份认证绕过漏洞复现(CVE-2024-11680)

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

Android笔记(三十四):onCreate执行Handler.post在onResume后才能执行?

背景 偶然发现一个点&#xff0c;就是在onCreate执行Handler.post在onResume后才执行&#xff0c;以下是测试代码 多次运行的结果一致&#xff0c;为什么execute runnable不是在onCreate和onResume之间执行的呢&#xff0c;带着疑问撸了一遍Activity启动流程 关键源码分析 …...

关闭模组的IP过滤功能

关闭模组的IP过滤功能 关闭模组的IP过滤功能 本脚本用于关闭模组的IP过滤功能&#xff0c;关闭后&#xff0c; 源地址不是终端IP的数据包&#xff0c;也可以被模组转发给网络 关闭模组的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对象…...

一番赏小程序定制开发,打造全新抽赏体验平台

随着盲盒的热潮来袭&#xff0c;作为传统的潮玩方式一番赏也再次受到了大家的关注&#xff0c;市场热度不断上升&#xff01; 一番赏能够让玩家百分百中奖&#xff0c;商品种类丰富、收藏价值高&#xff0c;拥有各种IP&#xff0c;从而吸引着各个圈子的粉丝玩家&#xff0c;用…...

【前端】将vue的方法挂载到window上供全局使用,也方便跟原生js做交互

【前端】将vue的方法挂载到window上供全局使用&#xff0c;也方便跟原生js做交互 <template><div><el-button click"start">调用方法</el-button></div> </template> <script> // import { JScallbackProc } from ./JScal…...

汽车生产虚拟实训中的技能提升与生产优化​

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

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

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

【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的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

C++使用 new 来创建动态数组

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

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...