[蓝桥杯 2022 省 B] 砍竹子 |
您所在的位置:网站首页 › 山上的竹子可以砍吗 › [蓝桥杯 2022 省 B] 砍竹子 |
题目描述
这天,小明在砍竹子,他面前有 n 棵竹子排成一排,一开始第 i 棵竹子的高度为 hi. 他觉得一棵一棵砍太慢了,决定使用魔法来砍竹子。魔法可以对连续的一段相同高度的竹子使用,假设这一段竹子的高度为 H,那么使用一次魔法可以把这一段竹子的高度都变为 ⌊sqrt( ⌊H/2⌋ +1)⌋, 其中 ⌊x⌋ 表示对 x 向下取整。小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。 输入格式第一行为一个正整数 n,表示竹子的棵数。 第二行共 n 个空格分开的正整数 hi,表示每棵竹子的高度。 输出格式一个整数表示答案。 输入输出样例输入 6 2 1 4 2 6 7输出 5 说明/提示【样例说明】 其中一种方案: 214267→214262→214222→211222→111222→111111214267→214262→214222→211222→111222→111111 共需要 5 步完成 【评测用例规模与约定】 对于 20%20% 的数据,保证 n≤1000,hi≤10^6 。 对于 100%100% 的数据,保证 n≤2×10^5,hi≤10^18 。 #include #include using namespace std; long long aa[200001]; long long bb[200001]; int main(){ int n; cin>>n; long long cnt=0,m=0; for(int i=0;i>aa[i]; long long h=aa[i]; while(h>1){ bb[i]++; h=sqrt(h/2+1); } m=max(m,bb[i]); } for(int k=m;k>0;k--){ for(int i=0; i |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |