数组至多K次floor除以2操作求最小和算法超时问题排查

首先，咱们来拆解下你的代码超时的核心原因，以及逻辑上的小问题：

1. 时间复杂度的致命问题 #

你的代码里每次操作后都会调用max(arr)来判断当前元素是不是最大值，这个操作的时间复杂度是O(n)。如果K的取值很大（比如1e5级别），同时数组长度n也不小的话，总时间复杂度会达到O(K*n)，这完全超出了时间限制的阈值，必然会触发Time Limit Exceeded。

举个例子：如果n=1e4，K=1e4，那总操作次数就是1e8，这在Python里肯定跑不完。

2. 逻辑上的小漏洞 #

你的排序后逐个处理的逻辑有问题：比如你处理完第一个最大元素（比如20→10），此时数组里的7可能比10小，但如果接下来你处理7→3，此时10又变成了最大的，但你的i已经递增到下一个位置，不会回头再处理10了——而要让数组和最小，每次必须操作当前数组中最大的元素（因为大的数除以2减少的幅度最大），你的逻辑会错过这类最优操作。

正确的优化思路：用最大堆（优先队列） #

要解决这个问题，我们需要一种能快速获取当前最大值的数据结构，也就是最大堆。Python的heapq模块默认是最小堆，我们可以通过存储负数来模拟最大堆，每次取出最小的负数（对应原数组的最大值），处理后再放回堆中。

修正后的代码 #

import heapq

n, k = map(int, input().split())
arr = list(map(int, input().split()))

# 用负数模拟最大堆
heap = [-num for num in arr]
heapq.heapify(heap)

for _ in range(k):
    current_max = -heapq.heappop(heap)
    current_max //= 2
    heapq.heappush(heap, -current_max)

# 求和：堆里的元素是负数，取反后相加
print(sum(-x for x in heap))

时间复杂度分析 #

• 初始化堆的时间是O(n)
• 每次弹出和插入堆的操作是O(logn)，K次操作就是O(Klogn)
• 总时间复杂度是O(n + Klogn)，即使K和n都是1e5级别，也能轻松通过时间限制。

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