求助：codeforces 251A - Points on Line

[zhangyu...@163.com]

求助各位，如何才能不超时啊？下述我的错误指令和代码。（上传至codeforces时请务必删除注释）

Test: #11, time: 2000 ms., memory: 5692 KB, exit code: -1, checker exit code: 0, verdict: TIME_LIMIT_EXCEEDED

from collections import deque

n,m = [int(i) for i in input().split()]

list_inp = input().split()

D = deque()

ways=0

#D用来储存相邻两个数之间的差值，ways用于统计可行的数量

 

for i in range(n-1):

    while sum(D)+int(list_inp[i+1])-int(list_inp[i])>m and len(D)>0:

        D.popleft()

#当D值总和即将超过m时，移除最开始的差值，直至符合要求或队列为空

    if sum(D)+int(list_inp[i+1])-int(list_inp[i]) <= m:

        ways += int(len(D)*(len(D)+1)/2)

        

#根据数学计算，每次进入一个差值时，共有如上组点符合要求

        

        D.append(int(list_inp[i+1])-int(list_inp[i]))

#再将上次的差值传入

        

print (ways)

    

[董自鸣]

sum(D)这个操作是O(n)的吧,你可以记录一个sum变量,不要每次都sum一遍

在 2016年3月30日星期三 UTC+8下午9:33:10，zhangyu...@163.com写道：

[zhangyu...@163.com]

非常感谢，已经解决！