题目描述
这天，小明在砍竹子，他面前有 n 棵竹子排成一排，一开始第 i 棵竹子的高度为 h_i.
他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为 H，那么使用一次魔法可以把这一段竹子的高度都变为 ⌊\sqrt{⌊\frac{H}{2} ⌋+1}⌋, 其中⌊x⌋ 表示对 x 向下取整。小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。
输入格式
第一行为一个正整数 n，表示竹子的棵数。
第二行共 n 个空格分开的正整数 h_i ，表示每棵竹子的高度。
输出格式
一个整数表示答案。
样例 #1
样例输入 #1
6
2 1 4 2 6 7
样例输出 #1
5
提示
【样例说明】
其中一种方案:
214267→214262→214222→211222→111222→111111
共需要 5 步完成
【评测用例规模与约定】
对于 20%的数据，保证 {n≤1000,h _i≤10^ 6} 。
对于 100%的数据，保证 n≤2×10^5,h _i≤10^{18} 。
题目思路
首先求出每一棵竹子需要处理的次数，并记录最大次数。
然后，运用贪心思想，从最大次数开始枚举，这里要注意的是处理次数相同并不代表高度相同（有向下取整），枚举的部分就比较简单了。
核心代码
//cnt[i]代表第i棵竹子的处理次数
int ans=0;
for(int i=max_cnt;i>0;i--)
{
for(int j=1;j<=n;j++)
{
if(cnt[j]==i)
{
if(height[j]!=height[j+1])ans++;
cnt[j]--;
height[j]=sqrtl(height[j]/2+1);
}
}
}