解题思路:
思路参考的大佬的思路,采用了差分法。说一下自己对这个方法的理解。
①建立一个数组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)
0.0分
0 人评分
【回文数(二)】 (C语言代码)浏览:856 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:1007 |
【蟠桃记】 (C语言代码)浏览:1035 |
完数 (C语言代码)浏览:693 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:587 |
2006年春浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:669 |
单词个数统计 (C语言代码)浏览:1012 |
1134题解(求分析)浏览:729 |
简单的a+b (C语言代码)浏览:510 |
简单的a+b (C语言代码)浏览:609 |