砍竹子(蓝桥杯 2022 省赛 B 组 J 题)

简介: 砍竹子(蓝桥杯 2022 省赛 B 组 J 题)

AC代码:

#include<iostream>
#include<queue>
#include<math.h>
using namespace std;
long long res;
struct node
{
  long long val,l, r;
};
bool operator <(node a, node b)
{
  return a.val == b.val ? a.l < b.l : a.val < b.val;//定义调堆的规则,如果值相等的情况下,优先考虑左区间大的
}
int main(void)
{
  long long n, k;
  priority_queue<node>p;//定义一个node类型的堆
  scanf("%lld", &n);
  for (int i = 1; i <= n; i++)
  {
    scanf("%lld", &k);
    p.push({ k,i,i });
  }
  while (p.top().val != 1)
  {
    node t = p.top();//取出当前的堆顶元素(最大值)
    p.pop();//先将最大值出堆,等砍掉之后还会将高度重新入堆
    node top;//用于等会记录堆中第二大的值
    while (!p.empty())
    {
      top = p.top();//堆中第二大的值
      if (t.val == top.val && t.l - 1 == top.r)//如果最大值和第二大的值相等,并且区间差只有1,就是相邻的竹子
      {
        p.pop();//一起砍掉,就是先pop掉第二大的,所有相等的且相邻的只用保留一个数就行了,当这个数被砍为1的时候相当于所有相邻的都被砍为1了
        t.l = top.l;//相当于合并区间了
      }
      else
      {
        break;//如果没有可以一并砍掉的就直接跳出循环
      }
    }
    int val = sqrtl(t.val / 2 + 1);//计算
    p.push({ val,t.l,t.r });//将砍了之后的高度加入堆中
    res++;//砍的次数+1
  }
  printf("%lld", res);
  return 0;
}


目录
相关文章
|
2月前
|
人工智能 C++
第十四届省赛大学B组(C/C++)接龙数列
第十四届省赛大学B组(C/C++)接龙数列
|
7月前
|
测试技术 C语言
第十四届蓝桥杯B组第一期模拟题
第十四届蓝桥杯B组第一期模拟题
57 0
|
算法 测试技术 C++
第十一届蓝桥杯第三场软件类省赛 C++ B组 题解(二)
第十一届蓝桥杯第三场软件类省赛 C++ B组 题解
161 0
|
算法 测试技术 C++
第十一届蓝桥杯第三场软件类省赛 C++ B组 题解(一)
第十一届蓝桥杯第三场软件类省赛 C++ B组 题解
108 0
|
人工智能 测试技术 C++
第十一届蓝桥杯大赛软件类决赛 C++ B组 题解(一)
第十一届蓝桥杯大赛软件类决赛 C++ B组 题解
202 0
|
机器学习/深度学习 人工智能 算法
第十一届蓝桥杯大赛软件类决赛 C++ B组 题解(二)
第十一届蓝桥杯大赛软件类决赛 C++ B组 题解
147 0
|
存储 算法
【蓝桥杯集训·每日一题】AcWing 3728. 城市通电
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 Prim算法
93 0
|
算法 C++ Windows
省赛将至,咱们看看第十一届蓝桥杯省赛C/C++ B组试题都出了些什么了?知己知彼,百战不殆
省赛将至,咱们看看第十一届蓝桥杯省赛C/C++ B组试题都出了些什么了?知己知彼,百战不殆
173 0
省赛将至,咱们看看第十一届蓝桥杯省赛C/C++ B组试题都出了些什么了?知己知彼,百战不殆