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;
}

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