---
title: "砍竹子"
created: 2025-11-28
tags:
  - 算法
---

# 砍竹子

## 题目  [砍竹子](https://www.acwing.com/problem/content/4412/)

![[image-d83fc435.png]]

## 思路分析

贪心猜对了大半 从最高的开始做

找到一颗最高的竹子 然后双指针检查左右是否有连续的一样高的 如果有 就全做一次砍的操作

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;

LL h[N];

int n;

bool check(LL a[]) {

    for (int i = 0; i < n; i++)

        if (a[i] != 1)

            return false;

    return true;

}

int main() {

    cin >> n;

    for (int i = 0; i < n; i++) {

        cin >> h[i];

    }

    int cnt = 0;

    while (!check(h)) {

        // 找到最高的竹子

        LL max_height = 0;

        int idx = -1;

        for (int i = 0; i < n; i++) {

            if (h[i] > max_height) {

                max_height = h[i];

                idx = i;

            }

        }

        // 使用双指针找到连续相同高度的竹子

        int l = idx - 1, r = idx + 1;

        while (l >= 0 && h[l] == h[idx])

            l--;

        while (r < n && h[r] == h[idx])

            r++;

        // 对这些竹子使用魔法

        LL new_height = floor(sqrt(max_height / 2 + 1));

        for (int i = l + 1; i < r; i++)

            h[i] = new_height;

        cnt++;

    }

    cout << cnt;

    return 0;

}
```

![[image-c7e04b3f.png]]

（给的真小气）

其实是忽略了一个地方 几个连续相同的是可以合并成一个的 不应该没想到 这个技巧在岛屿那题见过

这题多花些时间应该是能写出来的 10分钟不到基本思路就出来了

前年c++b组的最后一题 反观还没有前面几道贪心跳跃性强

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=2e5+10;

struct Seg{

    int l,r;

    LL v;

    bool operator<(const Seg& other)const{

        if(v!=other.v)

            return v<other.v;

        return l>other.l;

    }

};

priority_queue<Seg> heap;

LL h[N];

int n;

LL f(LL x)

{

    return sqrtl(x / 2 + 1);

}

int main()

{

    cin>>n;

    for(int i=0;i<n;i++)

        cin>>h[i];

    for(int i=0;i<n;i++){

        int j=i+1;

        while(j<n && h[i]==h[j])

            j++;

        heap.push({i,j-1,h[i]});

        i=j-1;

    }

    int cnt=0;

    while (heap.size()>1 || heap.top().v>1) {

        auto cut = heap.top();

        heap.pop();

        while(heap.size() && heap.top().v == cut.v && cut.r + 1 == heap.top().l)

        {

            cut.r = heap.top().r;//相邻且等高的合并

            heap.pop();

        }

        heap.push({cut.l, cut.r, f(cut.v)});

        if (cut.v > 1)

            cnt++;

    }

    cout<<cnt;

    return 0;

}
```

砍竹子

## 代码实现

```

```

## 同类题型

## 视频讲解

---
⬅️ [[疑难杂类|疑难杂类]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/贪心相关模型/疑难杂类/（50分 多路归并 二分）技能升级|（50分 多路归并 二分）技能升级]]