程序因超时而终止

给出一个大小为N的列表，用零初始化。您必须在列表中执行M个操作并输出列表中所有元素的最大值的最大值。对于每一个操作，你都有三个整数a，b和k，你必须为所有从索引a到b（包括两个端点）的元素增加值。

输入格式

第一行包含两个整数N和M由单个空格分开。下一行将包含由一个空格分隔的三个整数a，b和k。在列表数字编号从1到N

这是我写的代码：

n,m=map(int,input().split()) 
arr=[] 
for i in range(n+1): 
    arr.append(0) 
for j in range(m): 
    a,b,k=map(int,input().split()) 
    for i in range(a,b+1): 
     arr[i]+=k; 

print(max(arr))

当我试图提交我的解决方案，我收到了“由于终止TIMOUT” message.Could你应该提出一个策略来避免这些错误，并且解决这个问题。

提前致谢！

来源

2017-05-19 Raman

你能后的输入值也？ – zenwraight

你确定你应该这样做吗？ – Wombatz

不要遍历列表范围;而是再次使用map来增加指示的值。类似于

for j in range(m): 
    a,b,k=map(int,input().split()) 
    arr[a:b+1] = map(lambda <increment-by-k>, arr[a:b+1])

这应该让您的居民优化一举突破并节省一些时间。

来源

2017-05-19 00:39:58 Prune

至少在CPython中，带有'lambda'的'map'基本上总是比可以内联lambda体（避免每个函数调用开销）的等效listcomp或genexpr慢。除非输入很大，*和*映射函数是C中实现的内置函数（有时甚至不是那样），它几乎从不会超过listcomp/genexpr。 'arr [a：b + 1] = map（k .__ add__，arr [a：b + 1]）'_might_会更快，但我通常会用'a [a：b + 1] = [x +为了简单和可读性，在arr [a：b + 1]中为了x。分批工作是节省，但'map' +'lambda'将撤消一些收益。 – ShadowRanger

在Python 3.5.4中，映射似乎比lambda上的listcomp快一些。然而，我很想看到另一个答案 - 为后代写作？ – Prune

我会猜测你搞砸了你的基准;记住，'map'是懒惰的，所以如果你没有用完结果，它实际上并没有做任何工作。为了测试，我刚刚对'k = 2'，'arr = list（range（100））'使用了'ipython'的'％timeit -r5'，然后测试了三个语句list（map（lambda x：x + k，arr [10:60]））''''arr [10:60]中的x [x + k]''''和'list（map（k .__ add__，arr [10:60]））''。对于'map' +'lambda'，时序为6.43μs，对于listcomp为2.94μs，对于'map' + C内置函数，时序为2.91μs，这在我的经验中是非常典型的行为。 – ShadowRanger

您可能需要一种比O（M * N）复杂度更高的算法。

你可以把间隔时间分隔符的列表：

n,m=map(int,input().split()) 
intervals = [] 
arr = [0 for i in range(n)] 

for j in range(m): 
    a,b,k=map(int,input().split()) 
    intervals += [(str(a), "begin", k)] 
    intervals += [(str(b), "end", k)] 
intervals = sorted(intervals, key=lambda x: x[0]+x[1]) 

k, i = 0, 0 
for op in intervals: 
    ind = int(op[0]) 
    if op[1] == "begin": 
     while ind > i: 
      arr[i] += k 
      i += 1 
     k += op[2] 
    else: 
     while i <= ind: 
      arr[i] += k 
      i+= 1 
     k -= op[2] 

print(arr)

如果排序算法是O（MlogM），这是O（MlogM + N）

来源

2017-05-19 01:14:26 lukess

程序因超时而终止

回答

相关问题