爱奇艺2018.9.28笔试散散的树

我不是女神ヾ 2022-05-09 04:50 361阅读 0赞

# 题目描述 #

![在这里插入图片描述][70]  
**输入：**  
5 20  
4 42 40 26 46  
**输出：**  
36

锯子必须同时砍树；  
从树顶到锯子这段距离被砍下来当成木头，从树根到锯子这段距离留下原地。  
问锯子最高可以多高，但其实要刚好使砍下来的木头的总长为m，其实就只有一种锯子的高度能满足。

# 排序后遍历 #

n,m = map(int,input().split())
    li = list(map(int,input().split()))
    
    li = sorted(li,reverse=True)#降序排序
    li.append(0)#这样就能砍到最矮的树
    
    Times = 1#倍数
    result = 0#已经砍下的木头的总长
    
    if len(li) == 2:#只有一棵树，但后面加了个0
        print(li[0] - m)
    elif len(li) > 2:
        for i in range(1,len(li)):
            temp = (li[i-1] - li[i]) * Times
            tempResult = result + temp
            if tempResult >= m:
                if (m-result)%Times == 0:
                	last = (m-result)//Times
                else:
                	last = (m-result)/Times
                print(li[i-1]-last)        
                break
            else:
                result = tempResult
            Times += 1

![在这里插入图片描述][70 1]  
如上图所示，以样例输入为例。  
排降序后，**黑色数字**就是5颗树。  
**红色数字**代表相邻两棵树之间的高度差，**蓝色数字**代表在这个区间内可以砍到几棵树。  
**比如，如果锯子高度为42，那么只能锯下长度为4的木头，而这样的木头只有1根。而如果锯子高度为40，那么除了之前锯下的4\*1的木头，还有2\*2的木头可以锯下。**  
黄色数字，说明了这个累加的过程。  
由于8<20<50，所以锯子的高度肯定是在\[40,26\]这个区间内。

**算法的思想是：**  
每次循环中，考虑锯子的高度为li\[i\]，那么此时锯子能锯到从li\[0\]到li\[i-1\]这几棵树（li\[i\]这棵树刚好锯不到），然后算出当前锯子能砍下的木头的总长：  
1.如果这个总长还是小于m，那么i++，继续循环。  
2.如果这个总长大于等于m，那么循环停止。然后根据当前的i，计算锯子的高度。具体地来说：使用上一次循环`i-1`用的锯子所能砍下的树的总长`result`，`m-result`就是剩余需要砍下来的木头长度。`Times`就是当前能砍到几棵树。

前面的每次循环，代表区间\[ li\[i-1\] , li\[i\] \]的树都被完全砍掉了。  
最后一次循环i中，代表区间\[ li\[i-1\] , li\[i\] \]的树不是被完全砍掉的。因此用`m-result`除以`Times`就是当前区间需要砍掉的每根木头的长度`last`。`last`是可能为小数的，需要注意。  
最终结果便是，`li[i-1]-last`。

# 有高度相同的树 #

本来以为自己的代码不能处理，有高度相同的树的这种情况，但是经过测试，发现没有问题。  
因为虽然在两端相同的区间内，`result`不会进行累加（因为temp为0），但是最终总会遇到一个两端不同的区间，而此时`Times`也进行过了应该做的累加，所以`temp = (li[i-1] - li[i]) * Times`也会得到正确的`temp`。  
**输入：**  
4 8  
46 42 42 42  
**输出：**  
41

[70]: /images/20220509/2d280cb755554139a8a8ad689b2b5070.png
[70 1]: /images/20220509/97979d8f0ea943ab8e181e49249e5cab.png