526互联

砍竹子

发布时间 2023-07-30 23:36:26作者: o-Sakurajimamai-o

# [蓝桥杯 2022 省 B] 砍竹子

## 题目描述

这天，小明在砍竹子，他面前有 $n$ 棵竹子排成一排，一开始第 $i$ 棵竹子的高度为 $h_{i}$.

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

## 输入格式

第一行为一个正整数 $n$，表示竹子的棵数。

第二行共 $n$ 个空格分开的正整数 $h_{i}$，表示每棵竹子的高度。

## 输出格式

一个整数表示答案。

## 样例 #1

### 样例输入 #1

```
6
2 1 4 2 6 7
```

### 样例输出 #1

```
5
```

## 提示

**【样例说明】**

其中一种方案:

$214267\rightarrow 214262\rightarrow 214222\rightarrow 211222\rightarrow 111222\rightarrow 111111$

共需要 5 步完成

**【评测用例规模与约定】**

对于 $20 \%$ 的数据，保证 $n \leq 1000, h_{i} \leq 10^{6}$ 。

对于 $100 \%$ 的数据，保证 $n \leq 2 \times 10^{5}, h_{i} \leq 10^{18}$ 。

蓝桥杯 2022 省赛 B 组 J 题。

 

//[蓝桥杯 2022 省 B] 砍竹子
//计算出所有竹子砍到还剩一下的次数,然后取最大值,只需要循环这个最大值
//由于是从最大值开始循环的,所以所有的次数都能被计算上
//如果此时你需要砍,接下来判断后面的竹子有没有和你等高的,然后砍去;
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,a[N],w[N],res,num;
signed main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        int tmp=a[i];
        while(tmp-1) w[i]++,tmp=sqrt(tmp/2+1);
        num=max(num,w[i]);
    }
    for(int j=num;j>0;j--)
        for(int i=0;i<n;i++){
            if(w[i]==j){
                if(a[i]!=a[i+1]) res++;
                w[i]--,a[i]=sqrt(a[i]/2+1);
            }
        }
    cout<<res;
    return 0;
}