2040: [蓝桥杯2022初赛] 砍竹子（优先队列）_这天,小明在砍竹子,他面前有 nn 棵竹子排成一排,一开始第 ii 棵竹子的高度为 h_{i

2040: [蓝桥杯2022初赛] 砍竹子

内存限制：256 MB 时间限制：1 S 标准输入输出

题目类型：传统 评测方式：文本比较 上传者：外部导入

提交：137 通过：60

题目描述

这天，小明在砍竹子，他面前有 n 棵竹子排成一排，一开始第 i 棵竹子的高度为 hi.
他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。
魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为H，
那么使用一次魔法可以把这一段竹子的高度都变为：

其中 ⌊x⌋ 表示对 x 向下取整。

小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为1。

输入格式

第一行为一个正整数 n，表示竹子的棵数。
第二行共 n 个空格分开的正整数 hi，表示每棵竹子的高度。
20%的测试数据：n ≤ 1000; hi ≤ 10^6。
100%的测试数据：n ≤ 2 × 10^5; hi ≤ 10^18。

输出格式

一个整数表示答案。

输入样例 复制

6
2 1 4 2 6 7

输出样例 复制

5

数据范围与提示

其中一种方案：
2 1 4 2 6 7
→ 2 1 4 2 6 2
→ 2 1 4 2 2 2
→ 2 1 1 2 2 2
→ 1 1 1 2 2 2
→ 1 1 1 1 1 1
共需要 5 步完成。

 1)结构体实现的优先队列

/**
    1)结构体实现的优先队列
*/
/**
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <functional>
using namespace std;
typedef long long LL;
 
 
//可以在定义结构体(类）的时候就重载运算符，当然当重载的运算符是成员函数时，成员函数
//的（显示）参数数量比运算对象的数量少一个，this绑定到左侧运算对象；
//当不是成员函数的时候，要定义成友元函数，即在函数前加关键字 friend ,此时友元函数的参数
//和一般函数的数量一样
 
struct infor
{
    LL val;
    int pos;
//    friend bool operator < (const infor &a,const infor &b)    //非成员函数需要将其定义成友元函数函数
//    {
//        if(a.val!=b.val)
//            return a.val<b.val;
//        else
//            return a.pos<b.pos;
//    }
};
 
struct cmp
{
    bool operator () (const infor &a,const infor &b)
    {
        if(a.val!=b.val)
            return a.val<b.val;
        else
            return a.pos<b.pos;
    }
};
 
 
int main()
{
    int n;
    infor val;
   // priority_queue<infor> vec;
    priority_queue<infor,vector<infor> ,cmp> vec;
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        scanf("%lld",&val.val);
        val.pos=i;
        vec.push(val);
    }
    int sum=0;
    while(vec.top().val!=1)
    {
        infor top=vec.top();
        vec.pop();
        LL ans=floor(sqrt((top.val/2+1)*1.0));
        vec.push({ans,top.pos});
        int coun=1;
        while(vec.top().val==top.val&&vec.top().pos==top.pos-coun++)
        {
            infor temp=vec.top();
            vec.pop();
            vec.push({ans,temp.pos});
        }
        ++sum;
    }
    cout << sum << endl;
    return 0;
}
*/

 

 2) pair 容器实现的优先队列
    优先队列的优先级默认设置为数字大的优先级高

/**
   2) pair 容器实现的优先队列
    优先队列的优先级默认设置为数字大的优先级高
*/
/**
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
typedef  pair<long long ,int> pll;
 
 
int main()
{
    int n;
    pll val;
    priority_queue<pll> vec;
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        scanf("%lld",&val.first);
        val.second=i;
        if(val.first!=1)
            vec.push(val);
    }
 
    int sum=0;
    while(!vec.empty()&&vec.top().first!=1)
    {
        pll top=vec.top();
        vec.pop();
        long long ans=floor(sqrt((top.first/2+1)*1.0));
        if(ans!=1)
            vec.push({ans,top.second});
        int coun=1;
        while(!vec.empty()&&vec.top().first==top.first&&vec.top().second==top.second-coun++)
        {
            pll temp=vec.top();
            vec.pop();
            if(ans!=1)
                vec.push({ans,temp.second});
        }
        ++sum;
    }
    cout << sum << endl;
 
    return 0;
}*/

3) 先把一棵树砍掉所需要的次数累加起来，然后再减掉相邻相等的树；
    把每棵树每次砍掉之前的高度记录下来，由于是200000棵树，1e18高度的树
    砍到1的次数为6，因此可以开一个dp[500010][6]的数组来存储数据。

/**
   3) 先把一棵树砍掉所需要的次数累加起来，然后再减掉相邻相等的树；
    把每棵树每次砍掉之前的高度记录下来，由于是200000棵树，1e18高度的树
    砍到1的次数为6，因此可以开一个dp[500010][6]的数组来存储数据。
*/
 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn=200010,m=10;
LL dp[maxn][m];
 
int main()
{
    int n;
    scanf("%d",&n);
    LL sta[m],val,res=0;
    int ans=0;
    for(int i=0;i<n;++i)
    {
        int top=0;
        scanf("%lld",&val);
        while(val>1)    sta[++top]=val,val=sqrt(val/2+1);
        ans=max(ans,top);
        res+=top;
        for(int j=0;top>0;++j,--top)
            dp[i][j]=sta[top];
    }
 
    for(int i=0;i<ans;++i)
        for(int j=0;j<n-1;++j)
        {
            if(dp[j][i]&&dp[j][i]==dp[j+1][i])  //为什么此处只需要判断dp[j][i]>=1便可，因为dp[j][[i]
                res--;                          //最小的值都是2
        }
 
    cout << res << endl;
 
    return 0;
}