蓝桥杯 2022 省赛 B 组 J 题：砍竹子
[蓝桥杯 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}\) 。
题解
根据题意，我们可以得到两个结论:
1. 一颗竹子最多被砍伐 \(O(logh_i)\) 次后高度降为1
2. 若有连续几颗竹子高度相同，则施展一次“魔法”就能让这些竹子的高度一起下降
我们设置一个变量ans来储存操作次数。基于上述结论，我们将对每棵竹子每次操作后的高度记录在一个数组store中。再对竹子操作之前，可以先在数组store中查看该竹子是否和前面的竹子高度相同，若相同，则不必将ans自增。下面给出的代码的操作顺序是按照竹子的编号自小到大操作，但事实上的操作顺序应该是先将尽可能多的竹子变换为同一高度。尽管如此，两种操作顺序导致的最后结果是一致的。
#include <iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 200001;
//存树高
ll height[N];
//存储先前树的高度
vector <ll> store[N];
int n;
ll update(ll x)
{
return sqrt(x / 2 + 1);
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> height[i];
int ans = 0;
for(int i = 1; i <= n; i ++)
{
while(height[i] > 1)
{
bool flag = false;
for(unsigned int j = 0; j < store[i - 1].size(); j++)
{
ll temp = store[i - 1][j];
//先前已存在高度相同的竹子，因此不必自增ans了
if(height[i] == temp)
{
flag = true;
break;
}
}
if(!flag)
ans++;
store[i].push_back(height[i]);
height[i] = update(height[i]);
}
}
cout << ans;
return 0;
}