問題描述

這天, 小明在砍竹子, 他面前有?n?棵竹子排成一排, 一開始第?i?棵竹子的 高度為?hi?.

他覺得一棵一棵砍太慢了, 決定使用魔法來砍竹子。魔法可以對連續的一 段相同高度的竹子使用, 假設這一段竹子的高度為?H, 那么

用一次魔法可以 把這一段竹子的高度都變為??H2?+1?, 其中??x??表示對?x?向下取整。小明想 知道他最少使用多少次魔法可

讓所有的竹子的高度都變為 1 。

輸入格式

第一行為一個正整數?n, 表示竹子的棵數。

第二行共?n?個空格分開的正整數?hi, 表示每棵竹子的高度。

輸出格式

一個整數表示答案。

樣例輸入

6
2 1 4 2 6 7

?

樣例輸出

5

?

樣例說明

其中一種方案：

214262： 214267→214262→214222→211222→111222→111111?? ?共需要 5 步完成

評測用例規模與約定

對于?20%?的數據, 保證?n≤1000,hi≤106 。 對于?100%的數據, 保證?n≤2×105,hi≤1018 。

運行限制

• 最大運行時間：2s
• 最大運行內存: 256M
• ?

解題思路

這是一道不需要思考思維 要求實現細節的貪心思維題目

首先 易得一個貪心策略：優先砍所剩竹子中高度最大的竹子??砍完高度高的竹子后由于高度變低，所以可能會跟原來高度低的竹子一塊被砍? 所以策略后半部分為?盡可能制造出多的高度相同的連續竹子? 然后一起砍

實現細節：會卡sqrt的精度 只能過65%的數據

每次利用堆取出? 并記錄下最高竹子的長度和編號 之后利用長度相同 編號相鄰的竹子一起砍一次的策略 只砍一次 依次入堆

AC代碼展示

如果覺得有用 就點贊+收藏 關注一下吧

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<LL,int> PLI;
const int N=2e5+10;
int n;
LL x,res;
priority_queue<PLI> q;void solve(){while(!q.empty()){PLI t=q.top(); q.pop();LL t1=t.first; int t2=t.second;LL high=sqrtl(t1/2+1); //砍竹子//注意:此題會卡sqrt的精度 要用sqrtl 返回long doubleif(high!=1) q.push({high,t2});//其實也可以理解為 對連續且長度相同的樹的一列 就一起砍了 減少次數while(!q.empty()&&q.top().first==t1&&q.top().second==t2-1){t2--;q.pop();if(high!=1) q.push({high,t2}); //注意 放的時候 竹子的高度是砍過的 }res++; //出現高度不同或編號不連續 即不能連續砍時 就++一次 每次取出一顆樹 最后就會砍一次 只不過貪心一下是否可以一次多砍幾棵樹 }
}int main(){IOS;cin>>n;for(int i=0;i<n;i++){cin>>x;if(x!=1) q.push({x,i});} solve();cout<<res<<endl; return 0;
}

?

?