蓝桥杯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;
}

 

 

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

智能指针【C++11】

文章目录 智能指针std::auto_ptr std::unique_ptrstd::shared_ptrstd::shared_ptr的线程安全问题std::weak_ptr 智能指针 std::auto_ptr 管理权转移 auto_ptr是C98中引入的智能指针&#xff0c;auto_ptr通过管理权转移的方式解决智能指针的拷贝问题&#xff0c;保证一个资源…

Win11 24h2 不能正常ensp

Win11 24h2 不能正常ensp 因为Win11 24h2的内核大小更改&#xff0c;目前virtualbox在7.1.4中更新解决了。而ensp不支持5.2.44之后的virtualbox并已停止维护&#xff0c;不再进行5.2.44修复&#xff0c;virtualbox 5.2.24的ntdll文件sizeofimage问题&#xff0c;此问题导致ens…

使用GO--Swagger生成文档

概述 在前后端分离的项目中&#xff0c;后端配置swagger可以很好的帮助前端人员了解后端接口参数和数据传输。go-swagger 是一个功能全面且高性能的Go语言实现工具包&#xff0c;用于处理Swagger 2.0&#xff08;即OpenAPI 2.0&#xff09;规范。它提供了丰富的工具集&#x…

沃德云商协系统微信小程序PHP+Uniapp

“多组织”的云服务平台&#xff0c;打造总商会、总协会、总校友会、工商联等多组织无障碍沟通合作平台&#xff0c;让各大分会、各大分校友会、分组织实现轻松管理&#xff0c;线上宣传展示、商机挖掘、会员管理、会员服务、跨界交流等, 借助沃德云商协平台系统&#xff0c;让…

网站打开速度测试工具:互联网优化的得力助手

在信息飞速流转的互联网时代&#xff0c;网站如同企业与用户对话的窗口&#xff0c;其打开速度直接关乎用户体验&#xff0c;乃至业务的成败。所幸&#xff0c;一系列专业的网站打开速度测试工具应运而生&#xff0c;它们宛如幕后的技术侦探&#xff0c;精准剖析网站性能&#…

shell脚本实战案例

文章目录 实战第一坑功能说明脚本实现 实战第一坑 实战第一坑&#xff1a;在Windows系统写了一个脚本&#xff0c;比如上面&#xff0c;随后上传到服务&#xff0c;执行会报错 原因&#xff1a; 解决方案&#xff1a;在linux系统touch文件&#xff0c;并通过vim添加内容&…

Face2QR:可根据人脸图像生成二维码,还可以扫描,以后个人名片就这样用了!

今天给大家介绍的是一种专为生成个性化二维码而设计的新方法Face2QR&#xff0c;可以将美观、人脸识别和可扫描性完美地融合在一起。 下图展示为Face2QR 生成的面部图像&#xff08;第一行&#xff09;和二维码图像&#xff08;第二行&#xff09;。生成的二维码不仅忠实地保留…

数据结构---队列(Queue)

1. 简介 队列&#xff08;Queue&#xff09;是一种常用的数据结构&#xff0c;它遵循先进先出&#xff08;FIFO&#xff0c;First In First Out&#xff09;的原则。这意味着第一个进入队列的元素将是第一个被移除的元素。队列在计算机科学中有着广泛的应用&#xff0c;比如任…

玩游戏没有flash插件的解决方案(No Flash)

一、概述 在网页游戏开发领域&#xff0c;Flash和H5是两种主流的技术。Flash游戏曾经占据主导地位&#xff0c;但随着HTML5技术的发展和浏览器对Flash支持的逐渐减少&#xff0c;H5游戏逐渐成为主流。本教程将详细介绍Flash和H5的区别&#xff0c;并提供将Flash游戏转换为H5游戏…

如何查看电脑的屏幕刷新率?

1、按一下键盘的 win i 键&#xff0c;打开如下界面&#xff0c;选择【系统】&#xff1a; 2、选择【屏幕】-【高级显示设置】 如下位置&#xff0c;显示屏幕的刷新率&#xff1a;60Hz 如果可以更改&#xff0c;则选择更高的刷新率&#xff0c;有助于电脑使用起来界面更加流…

新书速览|循序渐进Node.js企业级开发实践

《循序渐进Node.js企业级开发实践》 1 本书内容 《循序渐进Node.js企业级开发实践》结合作者多年一线开发实践&#xff0c;系统地介绍了Node.js技术栈及其在企业级开发中的应用。全书共分5部分&#xff0c;第1部分基础知识&#xff08;第1&#xff5e;3章&#xff09;&#xf…

AUTOSAR AP和CP的安全要求规范(Safety Req)详细解读

一、规范的编制的背景原因 编制该规范的原因 确保系统安全性和可靠性 随着汽车电子系统日益复杂&#xff0c;功能不断增加&#xff0c;对安全性和可靠性的要求也越来越高。该规范为AUTOSAR平台在安全执行、配置、更新、信息交换、数据处理等多方面制定了明确要求&#xff0c;…

数仓技术hive与oracle对比(四)

问题处理 sqoop导入异常 将oracle数据库中的表&#xff0c;用sqoop导入hive时&#xff0c;如果表中字段值含有“&#xff0c;”&#xff0c;会导致导入hive后&#xff0c;每一行所有字段的内容都放在了第一个字段&#xff0c;其他字段均没有值。这是因为hive底层是以文件的形…

流网络等价性证明:边分解后的最大流保持不变

流网络等价性证明:边分解后的最大流保持不变 问题描述证明思路伪代码C 代码实现解释问题描述 在流网络中,证明将一条边分解为两条边所得到的是一个等价的网络。具体来说,假设流网络 $ G $ 包含边 $ (u, v) $,我们以如下方式创建一个新的流网络 $ G’ $: 创建一个新结点 $…

应用案例 | 船舶海洋: 水下无人航行器数字样机功能模型构建

水下无人航行器数字样机功能模型构建 一、项目背景 为响应水下装备系统研制数字化转型及装备系统数字样机建设的需要&#xff0c;以某型号水下无人航行器&#xff08;Underwater Unmanned Vehicle&#xff0c;UUV&#xff09;为例&#xff0c;构建UUV数字样机1.0功能模型。针对…

RabbitMQ七种工作模式之简单模式, 工作队列模式, 发布订阅模式, 路由模式, 通配符模式

文章目录 一. Simple(简单模式)公共代码:生产者:消费者: 二. Work Queue(工作队列模式)公共代码:生产者:消费者1, 消费者2(代码相同): 三. Publish/Subscribe(发布/订阅模式)公共代码:生产者:消费者: 四. Routing(路由模式)公共代码:消费者: 五. Topics(通配符模式)公共代码:生…

前端知识1html

VScode一些快捷键 Ctrl/——注释 !——生成html框架元素 *n——生成n个标签 直接书写html的名字回车生成对应的标签 常见标签 span&#xff1a; <span style"color: red;">hello</span> <span>demo</span> span实现&#xff1a; 标题…

Push an existing folder和Push an existing Git repository的区别

Push an existing folder 和 Push an existing Git repository 是在使用 Git 服务&#xff08;如 GitHub、GitLab、Bitbucket 等&#xff09;时两个常见的操作选项。它们的区别主要体现在项目的初始化和版本控制状态上&#xff1a; 1. Push an existing folder 适用场景&#…

Netty入门(快速了解以及使用netty)

二. Netty 入门 1. 概述 1.1 Netty 是什么&#xff1f; Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients.Netty 是一个异步的、基于事件驱动的网络应用框架&…

Zemax 中 ZBF 文件激光传播的描述

激光传播是指激光束在空间或介质中传播的方式。激光的独特特性&#xff0c;例如相干性、单色性和准直性&#xff0c;使其行为与普通光源不同。了解激光传播的原理在光学、通信、医疗技术和科学研究等领域至关重要。 激光产生高斯光束&#xff0c;其中强度在光束横截面上服从高…