Codeforces竞赛Python代码超时，如何进一步优化以通过时间限制？

最近参加编程竞赛时遇到一道数组处理题，要求遍历给定数组并输出结果数组。我先后尝试了三种实现方式：用for循环append元素后整体打印、预创建列表填充、循环内逐次打印，试图将时间复杂度降至O(n)，但所有方法都超出时间限制。不确定是Python本身效率问题，还是代码仍有优化空间，附上两段代码寻求建议。

初始代码 #

t = int(input())
for _ in range(t):
    n = int(input())
    v = list(map(int, input().split()))
    if n == 1:
        print(v[0])
    elif n == 2:
        print(v[0], int((v[1] + v[0])/2) * 2)
    else:
        w = [0 for l in range(n)]
        w[0] = v[0]
        w[1] = int((v[1] + v[0])/2) * 2
        c = 0
        if v[0] % 2:
            c += 1
        if v[1] % 2:
            c += 1
        b = 0
        for k in range(2, n):
            if v[k] % 2:
                c += 1
            b = int(c // 3)
            if c % 3 == 1:
                b += 1
            w[k] = (sum(v[:k + 1]) - b)
        print(*w)

循环内逐次打印的代码 #

t = int(input())
for _ in range(t):
    n = int(input())
    v = list(map(int, input().split()))
    if n == 1:
        print(v[0])
    elif n == 2:
        print(v[0], int((v[1] + v[0])/2) * 2)
    else:
        w = [0 for x in range(n)]
        w[0] = v[0]
        print(w[0], end=" ")
        w[1] = int((v[1] + v[0])/2) * 2
        print(w[1], end=" ")
        c = 0
        if v[0] % 2:
            c += 1
        if v[1] % 2:
            c += 1
        b = 0
        for k in range(2, n):
            if v[k] % 2:
                c += 1
            b = int(c // 3)
            if c % 3 == 1:
                b += 1
            w[k] = (sum(v[:k + 1]) - b)
            if k == n - 1:
                print(w[k])
            else:
                print(w[k], end=" ")

1. 修复时间复杂度隐患：两段代码中最致命的问题是sum(v[:k+1])，每次调用都会遍历从数组开头到k的所有元素，导致整个循环的时间复杂度变为O(n²)，这才是超时的核心原因。改用前缀和变量累加：

   • 初始化prefix_sum = v[0] + v[1]
   • 在循环中每次加上v[k]，避免重复求和

2. 优化输入读取：Python的input()函数速度较慢，对于大量输入的竞赛场景，改用sys.stdin.readline或一次性读取所有输入拆分，可以显著提升速度。

3. 优化输出方式：逐次print(..., end=" ")会产生多次IO操作，效率低下。建议将结果存入列表，最后用print(' '.join(map(str, result_list)))一次性输出。

4. 简化计算逻辑：int((v[1] + v[0])/2) * 2可以简化为(v[0] + v[1]) - ((v[0] + v[1]) % 2)，避免浮点数运算，提升效率。

优化后的示例代码：

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    t = int(input[ptr])
    ptr += 1
    for _ in range(t):
        n = int(input[ptr])
        ptr += 1
        v = list(map(int, input[ptr:ptr+n]))
        ptr += n
        res = []
        if n == 1:
            res.append(str(v[0]))
        elif n == 2:
            s = v[0] + v[1]
            res.append(str(v[0]))
            res.append(str(s - (s % 2)))
        else:
            res.append(str(v[0]))
            s = v[0] + v[1]
            res.append(str(s - (s % 2)))
            c = (v[0] % 2) + (v[1] % 2)
            prefix_sum = s
            for k in range(2, n):
                prefix_sum += v[k]
                if v[k] % 2:
                    c += 1
                b = c // 3
                if c % 3 == 1:
                    b += 1
                res.append(str(prefix_sum - b))
        print(' '.join(res))

if __name__ == "__main__":
    main()

内容的提问来源于stack exchange，提问作者Stony