划分树应用——HDU 4417 Super Mario——python3实现

浅浅的花香味﹌ 2022-05-22 12:22 88阅读 0赞

题目来自于[HDU 4417][]。划分树的代码及原理请看我写的这篇博客[划分树详解][Link 1]。

*  题目重述
 *  试题分析
 *  代码实现
 *  思考与总结

# 题目重述 #

【问题描述】：超级马里奥是世界著名水管工，可是他的公主被老板抓住了，所以马里奥就要去老板的城堡救他的公主。把到城堡的路线看成一条直线（长度为n），在每个整数点i，有一块高度为h的砖。现在的问题是，如果马里奥能跳的最大高度为h，那么在\[left,right\]区间里，马里奥有多少块砖能跳上去。  
【输入】：  
第一行给出两个整数n，m (1 <= n <=10^5, 1 <= m <= 10^5)，n是路的长度，m是查询次数  
下一行给出n个整数，表示在i位置上的砖的高度。  
接下来的m行，每行给出3个整数left、right、h。  
【输出】：  
有m行，每行只有一个数，代表第m查询马里奥能跳上去的砖的个数。  
【样例输入输出】：  
![这里写图片描述][70]

# 试题分析 #

采用二分查找+划分树可解决。若马里奥能够跳过高度为x的砖头，那么所有高度不大于x的砖头都能够跳过。这就凸显出问题的单调性，使得二分查找可以解决。

【1】比如\[left,right\]的长度为5，那么\[left,right\]排序后的数组，是由\[left,right\].1(代表第1大的值，即排升序后第1个数)，\[left,right\].2，\[left,right\].3，\[left,right\].4，\[left,right\].5。

【2】 因为已经有了划分树这个工具，所以\[left,right\].k只要调用一次划分树的查询query函数就可以直接得到。

【3】进行二分，(left+right)/2作为mid\_index，mid\_index与left间有3个数，那么就查询\[left,right\].3

【4】如果h>=\[left,right\].3，说明马里奥现在至少有3块砖能够跳过，因为\[left,right\].3是第3大的数

【5】left更新为left+3，right不变。继续二分，(left+right)/2作为mid\_index，mid\_index与left间有1个数（此时mid\_index等于left），上一次查了第3大，现在就查3+1大的数left,right\].4

【6】如果h>=\[left,right\].4，说明马里奥现在至少有4块砖能够跳过，因为\[left,right\].4是第4大的数

【7】left更新为left+1（4+1，这个1是指第5步中mid\_index与left间有1个数），right不变（此时left已变成最大索引right）。继续二分，(left+right)/2作为mid\_index，mid\_index与left间有1个数（此时mid\_index等于left等于right即最大索引）。上次查了第4大，现在就查4+1的数left,right\].5

【8】如果h>=\[left,right\].5，说明马里奥现在至少有5块砖能够跳过，因为\[left,right\].5是第5大的数。否则，说明马里奥只能跳过4个砖。

当然，如果第4步中，h<\[left,right\].3，说明现在马里奥能跳的高度，是小于第3大的数的。此时就应该减小搜索区间，再看看\[left,right\].2和\[left,right\].1的大小。  
【形式化说明】：给定\[s,t\]区间，得到\[s,t\]的长度n，每次查询第n/2大的数。如果高度h大于等于这个数，说明mario至少能跳n/2个数；如果小于，那么便缩小搜索区间，继续寻找。

# 代码实现 #

num = [0,5,2,7,5,4,3,8,7,7]#条件
    
    tree = []#二维列表，作为返回值
    sort = []#中间变量，是每一个节点的内的元素的排序
    
    toleft = []#二维列表，作为返回值
    
    def build(left,right,dep):
        if(left==right):#递归终点
            return
        if(dep==0):#第一次递归
            tree.append(num)
            toleft.append([False]*len(num))
        else:#不是第一次，当前层的tree不用建了，但toleft得建
            if(len(toleft)==(dep)):
                toleft.append([False]*len(num))        
        sort = tree[dep][left:right+1]
        sort.sort()#此处可能还能优化
        temp_mid = (len(sort)-1)//2
        sort_mid = sort[temp_mid]
    
        mid = (left+right)//2
        same = mid-left+1#现在是左子区间的长度
        for i in range(left,right+1):
            if(tree[dep][i] < sort_mid):
                same-=1#执行完此循环，便得到左子区间中，sort[mid]的个数
        lpos = left
        rpos = mid+1
        count = 0
        #接下来要为下一层建树，但tree[dep+1]这个list还没有建立，需要每次建立
        if(len(tree)==(dep+1)):
            tree.append([False]*len(num))
    
        for i in range(left,right+1):#tree的i，索引从0开始
            if(tree[dep][i] < sort_mid):
                tree[dep+1][lpos]=tree[dep][i]
                lpos+=1
                count+=1
            elif( (tree[dep][i] == sort_mid) and (same > 0) ):
                tree[dep+1][lpos]=tree[dep][i]
                lpos+=1
                same-=1
                count+=1
            else:
                tree[dep+1][rpos]=tree[dep][i]
                rpos+=1
            #上面每次把一个数加入到子区间内 
            toleft[dep][i] = count
    
        build(left,mid,dep+1)
        build(mid+1,right,dep+1)
    
    build(0,len(num)-1,0)
    
    for i in tree:
        print(i)
    print()
    for i in toleft:
        print(i)    
    print()
    
    def get_ant(toleft,L,R,left,right):
        #L>=left right<=R，这是已经成立的
        interval_left = 0#在[L,left-1]中进入到左子区间的数的个数
        interval_current = 0
    
        if(L<left):#此时在[left,right]的左边，会有一个左边区间
            interval_left = toleft[left-1]                       
        elif(L==left):#此时在[left,right]的左边，根本没有左边区间
            interval_left = 0
        interval_current = toleft[right]
        return (interval_current - interval_left,interval_left)
        #第二个值，当接下来递归到左子区间时，能用上
    
    
    
    def query(L,R,left,right,dep,k):
        if(left==right):
            return tree[dep][left]  
        mid = (L+R)//2
        cnt = get_ant(toleft[dep],L,R,left,right)
        #newl,newr是接下来要分析的left,right
        if(cnt[0]>=k):
            newl=L+cnt[1]
            newr=newl+cnt[0]-1
            return query(L,mid,newl,newr,dep+1,k)
        else:
            offset = (R-right) - (toleft[dep][R] - toleft[dep][right])
            newr = R - offset
            temp = right-left+1-cnt[0]
            newl = newr - temp + 1
            return query(mid+1,R,newl,newr,dep+1,k-cnt[0])
    
    
    def solve(n,s,t,h):
        ans = 0
    
        left = s
        right = t
    
        mid_index = (s+t)//2
        mid_length = mid_index-s+1
        #代表[left,right]区间长度的一半，一定是从这个初始值加减,也代表将要查询的第k大值 
    
        while(left<=right):
            #print(left,right)
            temp = query(0,n,s,t,0,mid_length)
            if(h>=temp):
                ans = mid_length
                if(left==right):#终点，但必须在ans赋值之后
                    break            
                left = mid_index+1
    
            else:
                if(left==right):#终点
                    break            
                right = mid_index
    
            mid_index = (left+right)//2 #取区间中间索引
            mid_length = mid_index-s+1 #取区间长度的一半
    
        return ans
    
    print(solve(len(num)-1,2,8,6))
    print(solve(len(num)-1,3,5,0))
    print(solve(len(num)-1,1,3,1))
    print(solve(len(num)-1,1,9,4))
    print(solve(len(num)-1,0,1,0))
    print(solve(len(num)-1,3,5,5))
    print(solve(len(num)-1,5,5,1))
    print(solve(len(num)-1,4,6,3))
    print(solve(len(num)-1,1,5,7))
    print(solve(len(num)-1,5,7,3))

运行结果：  
![这里写图片描述][70 1]  
solve函数是为解决此题的主函数，而之前的函数都是为了建树和建查询函数，来自[划分树详解][Link 1]。第一大段是tree二维数组，第二大段是toleft二维数组，第三大段是10次查询对应的结果，与预期的输出相同。

# 思考与总结 #

划分树在此题中，只是一个工具，用来查询\[left,right\].k即第k大值。递归的过程是和线段树，划分树一样的二分过程。

【1】在solve函数中的while循环里，其实每次left和right其实是代表把不确定大小的数，锁定在\[left,right\]中。第一次循环时锁定在第1大数和第right-left+1大数中，因为第一次什么信息都不知道呢；  
【2】在试题分析中第5,6步中，不确定大小的数就只在第4大到第5大的数中了；  
【3】在试题分析中第7,8步中，不确定大小的数就只在第5大的数中了。

[HDU 4417]: http://acm.hdu.edu.cn/showproblem.php?pid=4417
[Link 1]: https://blog.csdn.net/anlian523/article/details/80784568
[70]: /images/20220522/790bdd1d0c4e4fb68c649be65011c45a.png
[70 1]: /images/20220522/afe07b18b9e342feadd7516d671dfa2f.png