蓝桥杯 2022 省B 砍竹子

思路：

非常明显，这题是个贪心。因为这题是求最小操作次数，而且每次操作都会变小，所以肯定要优先操作大的元素，这样它变小之后才可能和其它元素一起操作以减少操作次数。

所以：建立两个数组，一个存竹子高度，一个存还能被砍的次数。读入完之后循环把序列中砍伐次数最大的竹子砍一次并记录砍伐次数。这里注意，区间修改的要求是相邻且高度相同，所以要判断砍伐次数最大的竹子是否相邻且高度相同，如果是那就一起砍了。

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

// 定义一个函数 cuts，用于计算给定高度的切割次数
long long cuts(long long height)
{
    long long x = (long long)sqrt(height / 2 + 1); // 利用平方根函数求切割次数
    return x; // 返回切割次数
}

int main(){
    int n;
    cin >> n; // 输入待处理的木板数量

    long long heights[n]; // 定义一个长为 n 的数组，用于存储各个木板的高度
    vector<long long> cutnum(n, 0); // 定义一个长度为 n 的向量，用于存储各个木板的切割次数，初始值为 0
    long long cutmax = 0; // 记录切割次数的最大值，初始化为 0

    // 循环读入每块木板的高度，并计算其切割次数
    for(int i = 0; i < n; i++)
    {
        cin >> heights[i]; // 输入当前木板的高度
        long long a = heights[i]; // 记录当前木板的高度
        // 循环计算当前木板的切割次数，直到高度为 1 为止
        while(a > 1)
        {
            cutnum[i]++; // 增加当前木板的切割次数
            a = cuts(a); // 计算下一次切割后的木板高度
        }
        cutmax = max(cutmax, cutnum[i]); // 更新切割次数的最大值
    }

    int count = 0; // 计数变量，用于统计最终需要的切割次数

    // 从切割次数最大值开始向下遍历
    for(long long i = cutmax; i > 0; i--)
    {
        // 遍历每块木板
        for(int j = 0; j < n; j++)
        {
            // 如果当前木板的切割次数等于当前遍历的次数 i
            if(cutnum[j] == i)
            {
                // 如果当前木板的高度与下一块木板的高度不相等
                if(heights[j] != heights[j+1])
                    count++; // 增加切割计数
                cutnum[j]--; // 减少当前木板的切割次数
                heights[j] = cuts(heights[j]); // 更新当前木板的高度为切割后的高度
            }
        }
    }
    cout << count; // 输出最终切割次数
    return 0;
}