2040: [Blue Bridge Cup 2022 preliminary] bamboo cutting (priority queue)

2040: [ Blue Bridge Cup 2022 Preliminaries ] Cut bamboo

Memory limit ：256 MB The time limit ：1 S Standard input and output

Topic type ： Tradition Evaluation method ： Text comparison Uploaded by ： External import

Submit ：137 adopt ：60

Title Description

On the day , Xiao Ming is cutting bamboo , In front of him is n Bamboo trees stand in a row , At first i The height of each bamboo is hi.
He thought it was too slow to cut one by one , Decided to use magic to cut bamboo .
Magic can be used on a continuous section of bamboo of the same height , Suppose the height of this section of bamboo is H,
Then using magic once can change the height of this section of bamboo into ：

among ⌊x⌋ Said to x Rounding down .

Xiao Ming wants to know how many times he can use magic at least to make the height of all bamboos become 1.

Input format

The first line is a positive integer n, Indicates the number of bamboos .
The second line is n A positive integer separated by spaces hi, Indicates the height of each bamboo tree .
20% Test data for ：n ≤ 1000; hi ≤ 10^6.
100% Test data for ：n ≤ 2 × 10^5; hi ≤ 10^18.

Output format

An integer represents the answer .

sample input Copy

6
2 1 4 2 6 7

sample output Copy

5

Data range and tips

One of them is ：
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
A common need 5 Step through .

 1) The priority queue implemented by the structure

/**
    1) The priority queue implemented by the structure 
*/
/**
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <functional>
using namespace std;
typedef long long LL;


// You can define the structure ( class ） The operator is overloaded when , Of course, when the overloaded operator is a member function , Member functions 
// Of （ Show ） The number of parameters is one less than the number of operands ,this Bind to left operand ;
// When it is not a member function , To define as a friend function , That is, add the keyword before the function  friend , At this point, the parameters of the friend function 
// And the number of general functions is the same 

struct infor
{
    LL val;
    int pos;
//    friend bool operator < (const infor &a,const infor &b)    // Nonmember functions need to be defined as friend functions 
//    {
//        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 Priority queue implemented by container
    By default, the priority of priority queue is set to high priority if the number is large

/**
   2) pair  Priority queue implemented by container 
     By default, the priority of priority queue is set to high priority if the number is large 
*/
/**
#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) First add up the number of times it takes to cut down a tree , Then subtract the adjacent equal trees ;
    Record the height of each tree before each cut , Because it is 200000 tree ,1e18 High tree
    Cut to 1 Times of 6, So you can open a dp[500010][6] To store data .

/**
   3)  First add up the number of times it takes to cut down a tree , Then subtract the adjacent equal trees ;
     Record the height of each tree before each cut , Because it is 200000 tree ,1e18 High tree 
     Cut to 1 Times of 6, So you can open a dp[500010][6] To store data .
*/

#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])  // Why only need to judge here dp[j][i]>=1 Can then , because dp[j][[i]
                res--;                          // The minimum values are 2
        }

    cout << res << endl;

    return 0;
}