Python实现Codechef SNAKEEAT题超时，如何优化到10秒内运行

原代码超时核心原因 #

原代码时间复杂度过高，无法处理大数量级的测试用例，具体问题包括：

• 每个查询都复制全量长度数组、单独排序，单次查询时间复杂度达到O(N log N)，查询次数多的话总复杂度会飙升到O(Q*N log N)
• 频繁调用remove、pop(0)这类数组操作，这类操作本身是O(N)复杂度，进一步拖慢运行速度
• 输入输出用默认的input、print，对于大数据量场景效率极低

优化思路 #

利用题目特性把时间复杂度降到O(N log N + Q log N)，完全可以在10秒内跑完最大用例：

1. 全局只做一次预处理：把蛇的长度数组升序排序，同时计算前缀和数组，方便O(1)计算任意区间的长度和
2. 每个查询用二分法找最优解：对于给定的目标长度x，我们要找到最多能让多少条蛇达到长度x。最优策略是优先保留最长的m条蛇，此时需要的额外食物总量为 m*x - 最长m条蛇的总长度，只要这个值 <= 剩下的蛇的数量（可以全部用来当食物），这个m就是可行的。我们可以通过二分m的取值快速找到最大可行值
3. 输入输出优化：一次性读入所有输入数据，所有查询结果攒成列表后一次性输出，避免多次IO的开销

优化后代码 #

import sys
def main():
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    T = int(data[ptr])
    ptr += 1
    res = []
    for _ in range(T):
        N = int(data[ptr])
        Q = int(data[ptr+1])
        ptr += 2
        L = list(map(int, data[ptr:ptr+N]))
        ptr += N
        L.sort()
        # 计算前缀和
        pre_sum = [0]*(N+1)
        for i in range(N):
            pre_sum[i+1] = pre_sum[i] + L[i]
        # 处理所有查询
        for __ in range(Q):
            x = int(data[ptr])
            ptr += 1
            # 二分找最小的p，满足 (N-p)*x - (pre_sum[N]-pre_sum[p]) <= p
            left = 0
            right = N
            ans_p = N
            while left <= right:
                mid = (left + right) // 2
                m = N - mid
                need = m * x - (pre_sum[N] - pre_sum[mid])
                if need <= mid:
                    ans_p = mid
                    right = mid - 1
                else:
                    left = mid + 1
            res.append(str(N - ans_p))
    print('\n'.join(res))
if __name__ == "__main__":
    main()

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