西安o2o网站设计公司,用家里的路由器做网站,网络需求分析的主要内容有哪些,博物馆网站 微信 微博 建设问题描述
这天, 小明在砍竹子, 他面前有 n 棵竹子排成一排, 一开始第 i 棵竹子的 高度为 hi.
他觉得一棵一棵砍太慢了, 决定使用魔法来砍竹子。魔法可以对连续的一 段相同高度的竹子使用, 假设这一段竹子的高度为 H, 那么
用一次魔法可以 把这一段竹子的高度都变为 ⌊H2⌋…问题描述
这天, 小明在砍竹子, 他面前有 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 pairLL,int PLI;
const int N2e510;
int n;
LL x,res;
priority_queuePLI q;void solve(){while(!q.empty()){PLI tq.top(); q.pop();LL t1t.first; int t2t.second;LL highsqrtl(t1/21); //砍竹子//注意:此题会卡sqrt的精度 要用sqrtl 返回long doubleif(high!1) q.push({high,t2});//其实也可以理解为 对连续且长度相同的树的一列 就一起砍了 减少次数while(!q.empty()q.top().firstt1q.top().secondt2-1){t2--;q.pop();if(high!1) q.push({high,t2}); //注意 放的时候 竹子的高度是砍过的 }res; //出现高度不同或编号不连续 即不能连续砍时 就一次 每次取出一颗树 最后就会砍一次 只不过贪心一下是否可以一次多砍几棵树 }
}int main(){IOS;cinn;for(int i0;in;i){cinx;if(x!1) q.push({x,i});} solve();coutresendl; return 0;
}
