标签：int ll 高度 height 蓝桥 竹子 store

蓝桥杯 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;
}

时间复杂度为\(O(nlog^2n)\).

标签：int,ll,高度,height,蓝桥,竹子,store
From： https://www.cnblogs.com/parallel-138/p/17249663.html