python-蓝桥杯算法提高VIP-分苹果

解题思路:

思路参考的大佬的思路，采用了差分法。说一下自己对这个方法的理解。

①建立一个数组dis[n+2]，里面存储的值是每个小朋友与上一个小朋友手里的苹果的差值，初始化值为0。

   每发一次苹果，

        dis[l] = dis[l] + c

        dis[r+1] = dis[r+1] - c

②假设此处每个小朋友手里的苹果用数组chd[]表示，初始化chd[1] = dis[1]，

    由①可知，dis[i] = chd[i] - chd[i-1]，

    从而得知，chd[i] = chd[i-1] + dis[i]

注意事项:

本题代码超时，只得了64分。代码时间复杂度和用c++写的应该是差不多O(m+n)，个人感觉会超时可能是因为python列表查询速度慢的原因，目前还没有想到更好的解决方法，仅供参考，希望大家多多指点。

参考代码:

def f(n,m):  
    dis = [0 for i in range(n+2)]  
    chd = [0 for i in range(0,n+1)]  
  
    for i in range(m):  
        l,r,c = map(int,input().split())  
        dis[l] = dis[l] + c  
        dis[r+1] = dis[r+1] - c  
  
    chd[1] = dis[1]  
    for i in range(1,n+1):  
        chd[i] = chd[i-1] + dis[i]  
        print(chd[i],end = ' ')  
  
  
if __name__ == '__main__':  
    n,m = map(int,input().split())  
    f(n,m)