程序因超時而終止

給出一個大小爲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

程序因超時而終止

回答

相關問題