Python: 砍竹子(栈)

问题描述

这天, 小张在砍竹子, 他面前有 n 棵竹子排成一排, 一开始第 i 棵竹子的 高度为 hi​.

他觉得一棵一棵砍太慢了, 决定使用魔法来砍竹子。魔法可以对连续的一 段相同高度的竹子使用, 假设这一段竹子的高度为 H, 那么

用一次魔法可以 把这一段竹子的高度都变为 ⌊根号下⌊2H​⌋+1​⌋, 其中 ⌊x⌋ 表示对 x 向下取整。小张想 知道他最少使用多少次魔法可

让所有的竹子的高度都变为 1 。⌊2H​⌋+1​⌋

输入格式

第一行为一个正整数 n, 表示竹子的棵数。

第二行共 n 个空格分开的正整数 hi​, 表示每棵竹子的高度。

输出格式

一个整数表示答案。

样例输入

6
2 1 4 2 6 7

样例输出

5

样例说明

其中一种方案

2 1 4 2 6

→214262

→214222

→211222

→111222

→111111​

共需要 5 步完成

评测用例规模与约定

对于 20% 的数据, 保证 n≤1000,hi​≤10^6 。 对于 100% 的数据, 保证 n ≤ 2×10^5,hi ​≤ 10^18 。

思考 

        首先计算最多砍多少刀计算每棵竹子砍到1需要多少刀所有竹子砍数相加得到一个总数记为sum;   x记录每棵竹子每次被砍后的新高度
比较任意两个相邻的竹子它们是否有相同的高度如果有相同的高度这两棵竹子接下来可以一起砍,从而少砍一刀sum减一;
比较结束后sum就是答案。

        f [ ][ ]记录每棵竹子被砍后的高度f [ i ][ j ]记录第i棵竹子被砍后的高度f [ i ][ 0 ]是砍最后一刀后的高度f [ i ][top]是第一次被砍后的高度。

        用手写栈 s[ ] 记录砍每刀后的高度然后赋值给f [ i ][ ]。x比较任意两棵相邻竹子的高度如果有某个高度相等可以一起砍从而少砍一刀。

参考代码 

from math import *
f=[[0]*10 for _ in range(200010)]  #二维数组初始化
s=[0]*10                           #一维数组初始化
n=int(input())
a=list(map(int,input().split()))
sum=0
for i in range(n):
    x=a[i] 
    top=0  
    while x>1:   #计算每棵竹子最多砍多少刀用魔法分别砍一定最多
        top+=1  
        s[top]=x 
        x=floor(sqrt(floor(x/2)+1)) #floor()向下取整,1.98向下取整为1x为每棵竹子被砍后的高度
    sum+=top  
    k=top     
    j=0
    while k>0:
        f[i][j]=s[k]  #砍后的高度赋值给f[i][j]
        k-=1     
        j+=1     
for j in range(10):
    for i in range(1,n):
        if f[i][j]>0 and f[i][j]==f[i-1][j]: #比较任意两颗竹子的高度
            sum-=1         #若相等则少砍一刀
print(sum)