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

题目描述
这天，小明在砍竹子，他面前有 n 棵竹子排成一排，一开始第 i 棵竹子的高度为 hi​.

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

输入格式
第一行为一个正整数 n，表示竹子的棵数。

第二行共 n 个空格分开的正整数 hi​，表示每棵竹子的高度。

输出格式
一个整数表示答案。

输入输出样例
输入 #1

6
2 1 4 2 6 7
输出 #1

5

#include<bits/stdc++.h>
using namespace std;

long long oper(long long x){ // 魔法操作函数
    double v1 = x*1.0;
    v1 = floor(v1/2)+1;
    v1 = sqrt(v1);
    v1 = floor(v1);
    x = v1;
    return x;
}

int main(){
    long long n, ans = 0;
    cin>>n;
    vector<long long> arr(n); // 记录竹子高度
    for(long long i = 0; i<n; i++){
        cin>>arr[i];
    }
    
    vector<long long> oper_time(n, 0); // 记录竹子高度变为1所需操作次数
    for(long long i = 0; i < n; i++){
        long long temp = arr[i];
        while(temp > 1){
            oper_time[i]++;
            temp = oper(temp);
        }
    }
    
    long long max = *max_element(oper_time.begin(), oper_time.end()); // 找到操作数最大值
    
    for(long long i = max; i > 0; i--){ // 从最大操作数依次向下遍历
        for(long long j = 0; j < n; j++){
            if(oper_time[j] == i){ // 对于当前操作数
                if(j+1 >= n || arr[j] != arr[j+1]){ // 如果是数组末尾或与下一个竹子高度不同，则结束这一段的操作
                    ans++;
                }
                oper_time[j]--;
                arr[j] = oper(arr[j]);
            }
        }
    }
    
    cout<<ans;
    return 0;
}

对于这题，我们可以尝试将处理较麻烦的操作次数提前存储好，随后对于每个可能的操作次数进行遍历，寻找其中的可操作竹段