J 砍竹子

砍竹子

【问题描述】
这天,小明在砍竹子,他面前有 n 棵竹子排成一排,一开始第 i 棵竹子的高度为 hi .

他觉得一棵一棵砍太慢了,决定使用魔法来砍竹子。魔法可以对连续的一段相同高度的竹子使用,假设这一段竹子的高度为 H,那么使用一次魔法可以把这一段竹子的高度都变为 [ sqrt( [H / 2] + 1 ) ] ,其中 [x] 表示对 x 向下取整。小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。

【输入格式】
第一行为一个正整数n,表示竹子的棵数。
第二行共n个空格分开的正整数h,表示每棵竹子的高度。

【输出格式】
一个整数表示答案。

【样例输入】
6
2 1 4 2 6 7
1
2

【样例输出】
5
1

【样例说明】
其中一种方案: 2 1 4 2 6 7
→2 1 4 2 6 2
→2 1 4 2 2 2
→2 1 1 2 2 2
→1 1 1 2 2 2
→1 1 1 1 1 1
共需要5步完成

【评测用例规模与约定】

对于20%的数据,保证 n ≤ 1000, hi ≤ 10^6。
对于100%的数据,保证 n ≤ 2 × 10^5, hi ≤ 10^18。

题解

思路:
在这里插入图片描述
如图,首先,1e18的高度也最多只要砍6下,用m维护单个竹子最多砍几下,res则是若一棵一棵砍总共砍多少下,然后每一个用栈然后保存到数组中,即每个结点保存每棵树被砍到1会经历的高度,且随着数组中随着下标增大而增大,即上图中结点下面的部分是高度较低的,然后如果高度是相同的必在同一结点深度,但在同一结点深度不一定高度相同,判断再用res减去即可。

注意:本题是longlong,用sqrt精度不够,要用sqrtl

另:关于sqrt函数
sqrtf() 返回效率更高,精度最低
sqrt() 最常用,返回效率中等,精度中等
sqrtl() 返回效率较低,精度最高

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200006][10];
ll magic(ll x)
{
  return sqrtl(x/2+1);
}
int main()
{
  ll n,res=0,m=0;
  cin>>n;
  ll stk[10];
  for(int i=0;i<n;i++)
  {
    ll x;
    scanf("%lld",&x);
    ll top=0;
    while(x>1) 
    {
      stk[++top]=x;
      x=magic(x);
    }
    for(int j=0,k=top;k>0;j++,k--) a[i][j]=stk[k];
    res+=top;
    m=max(m,top);
  }
  for(int i=0;i<m;i++)
  {
    for(int j=1;j<n;j++)
    {
      if(a[j][i]>0&&a[j][i]==a[j-1][i]) res--;
    }
  }
  cout<<res<<endl;
  return 0;
}

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

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

相关文章

菜鸟刷题Day5

⭐作者&#xff1a;别动我的饭 ⭐专栏&#xff1a;菜鸟刷题 ⭐标语&#xff1a;悟已往之不谏&#xff0c;知来者之可追 一.一维数组的动态和&#xff1a;1480. 一维数组的动态和 - 力扣&#xff08;LeetCode&#xff09; 描述 给你一个数组 nums 。数组「动态和」的计算公式…

为了之后找工作不被虐,每天刷3道《剑指offer》Day-1

本文已收录于专栏&#x1f33b;《刷题笔记》文章目录前言&#x1f496; 1、二维数组中的查找题目描述思路&#x1f496; 2、替换空格题目描述思路&#x1f496; 3、从尾到头打印链表题目描述思路一&#xff08;反转函数&#xff09;思路二&#xff08;递归&#xff09;思路二&a…

Celery使用:优秀的python异步任务框架

目录Celery 简介介绍安装基本使用Flask使用Celery异步任务定时任务Celery使用Flask上下文进阶使用参考停止Worker后台运行Celery 简介 介绍 Celery 是一个简单、灵活且可靠的&#xff0c;处理大量消息的分布式系统&#xff0c;并且提供维护这样一个系统的必需工具。 它是一个…

文心一言 vs GPT-4 —— 全面横向比较

文心一言 vs GPT-4 —— 全面横向比较 3月15日凌晨&#xff0c;OpenAI发布“迄今为止功能最强大的模型”——GPT-4。我第一时间为大家奉上了体验报告《OpenAI 发布GPT-4——全网抢先体验》。 时隔一日&#xff0c;3月16日下午百度发布大语言模型——文心一言。发布会上&#…

4万字企业数字化转型大数据湖项目建设和运营综合解决方案WORD

本资料来源公开网络&#xff0c;仅供个人学习&#xff0c;请勿商用&#xff0c;如有侵权请联系删除。部分资料内容&#xff1a; 3.1.4沙盒管理 利用Docker, 基于kubernetes主打的容器技术与微服务应用基础平台&#xff0c;HDFS和YARN均可依此建模&#xff0c;为上层应用提供微服…

不愧是2023年就业最难的一年,还好有车企顶着~

就业龙卷风已经来临&#xff0c;以前都说找不到好的工作就去送外卖&#xff0c;但如今外卖骑手行业都已经接近饱和状态了&#xff0c;而且骑手们的学历也不低&#xff0c;本科学历都快达到了30%了&#xff0c;今年可以说是最难找到工作的一年。 像Android 开发行业原本就属于在…

学习 Python 之 Pygame 开发魂斗罗(十)

学习 Python 之 Pygame 开发魂斗罗&#xff08;十&#xff09;继续编写魂斗罗1. 解决敌人不开火的问题2. 创建爆炸效果类3. 为敌人跳入河中增加爆炸效果4. 玩家击中敌人继续编写魂斗罗 在上次的博客学习 Python 之 Pygame 开发魂斗罗&#xff08;九&#xff09;中&#xff0c;…

深度长文 | 数据安全共享技术发展综述及在能源电力领域应用研究

开放隐私计算 编者按数据要素的流通共享与协同应用是数字时代中数据要素市场培育的核心内容&#xff0c;数据安全共享技术能够有效实现数据的安全共享&#xff0c;避免“数据孤岛”现象、隐私泄露事件等.本文对国内外数据安全共享技术研究成果及进展进行了全面综述.首先&#x…

[前端笔记037]vue2之vuex

前言 本笔记参考视频&#xff0c;尚硅谷:BV1Zy4y1K7SH p105 - p116 vuex简介和基本使用 概念&#xff1a;专门在 Vue 中实现集中式状态&#xff08;数据&#xff09;管理的一个 Vue 插件&#xff0c;对 vue 应用中多个组件的共享状态进行集中式的管理&#xff08;读/写&…

CVPR 2023 | 旷视研究院入选论文亮点解读

近日&#xff0c;CVPR 2023 论文接收结果出炉。近年来&#xff0c;CVPR 的投稿数量持续增加&#xff0c;今年收到有效投稿 9155 篇&#xff0c;和 CVPR 2022 相比增加 12%&#xff0c;创历史新高。最终&#xff0c;大会收录论文 2360 篇&#xff0c;接收率为 25.78 %。本次&…

烤鱼界头牌半天妖发文致歉,背后暴露了哪些问题?

3月24日&#xff0c;半天妖烤鱼官方针对“两家门店食品安全问题”&#xff0c;发表致歉声明&#xff0c;并宣布将两家涉事门店永久关停。半天妖烤鱼爆出的食品安全问题再次提醒我们&#xff0c;加强门店监管和管理工作&#xff0c;保障消费者的健康和安全&#xff0c;成为了行业…

7.避免不必要的渲染

目录 1 组件更新机制 2 虚拟DOM配合Diff算法 3 减轻state 4 shouldComponentUpdate() 4.1 基本使用 4.2 使用参数 5 纯组件 5.1 基本使用 5.2 纯组件的比较方法 shallow compere 1 组件更新机制 当父组件重新渲染时&#xff0c;父组件的所有子组件也会重新…

如何理解AQS

AQS核心数据结构 AQS内部主要维护了一个FIFO&#xff08;先进先出&#xff09;的双向链表。 AQS数据结构原理 AQS内部维护的双向链表中的各个节点分别指向直接的前驱节点和直接的后续节点。所以&#xff0c;在AQS内部维护的双向链表可以从其中的任意一个节点遍历前驱结点和后…

【尝鲜版】ChatGPT插件开发指南

3月23日&#xff0c;OpenAI官方发布了一则公告&#xff0c;宣告ChatGPT已经支持了插件功能&#xff0c;现在处于内测阶段。插件的意义不仅仅在于功能的扩展&#xff0c;它直接让ChatGTP拥有了联网的能力&#xff01;简直是猛兽出笼、蛟龙出海&#xff0c;要让ChatGPT大杀特杀啊…

phpstorm断点调试

环境&#xff1a;win10phpstorm2022phpstudy8lnmp 1、phpinfo(); 查看是否安装xdebug&#xff0c;没有走以下流程 2、phpstudy中切换不同版本php版本&#xff0c;有些版本不支持xdebug&#xff08;如php8.0.2&#xff09;&#xff0c;有些已经自带了&#xff08;如php7.3.9&a…

Java奠基】Java经典案例讲解

目录 卖飞机票 找质数 开发验证码 数组元素的复制 评委打分 数字加密 数字解密 抢红包 模拟双色球 二维数组 卖飞机票 需求&#xff1a;机票价格按照淡季旺季、头等舱和经济舱收费、输入机票原价、月份和头等舱或经济舱。按照如下规则计算机票价格&#xff1a; 旺季&…

技术分享——Java8新特性

技术分享——Java8新特性1.背景2. 新特性主要内容3. Lambda表达式4. 四大内置核心函数式接口4.1 Consumer<T>消费型接口4.2 Supplier<T>供给型接口4.3 Function<T,R>函数型接口4.4 Predicate<T> 断定型接口5. Stream流操作5.1 什么是流以及流的类型5.2…

[攻城狮计划]如何优雅的在RA2E1上运行RT_Thread

文章目录[攻城狮计划]|如何优雅的在RA2E1上运行RT_Thread准备阶段&#x1f697;开发板&#x1f697;开发环境&#x1f697;下载BSP&#x1f697;编译烧录连接串口总结[攻城狮计划]|如何优雅的在RA2E1上运行RT_Thread &#x1f680;&#x1f680;开启攻城狮的成长之旅&#xff0…

【ChatGPT】教你搭建多任务模型

ChatGPT教你搭建多任务模型 You: tell me what’s your version of gpt ? ChatGPT: As an AI language model developed by OpenAI, I am based on the GPT (Generative Pretrained Transformer) architecture. However, my version is known as GPT-3.5, which is an updat…

数据泄漏防护 (DLP) 工具保护敏感数据

通过实时安全监控&#xff0c;通过端点&#xff08;即 USB、电子邮件、打印等&#xff09;检测、中断和防止敏感数据泄露。使用 DataSecurity Plus 的数据泄漏防护 &#xff08;DLP&#xff09; 工具保护敏感数据不被泄露或被盗。DataSecurity Plus 主要功能包括&#xff1a; …