解题思路:
思路参考的大佬的思路,采用了差分法。说一下自己对这个方法的理解。
①建立一个数组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 人评分
点我有惊喜!你懂得!浏览:1088 |
C语言训练-阶乘和数* (C语言代码)浏览:1007 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:470 |
C语言训练-求素数问题 (C语言代码)浏览:729 |
printf基础练习2 (C语言代码)浏览:305 |
C二级辅导-阶乘数列 (C语言代码)浏览:694 |
C语言程序设计教程(第三版)课后习题6.11 (C语言代码)浏览:549 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:1099 |
简单的a+b (C语言代码)浏览:548 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:551 |