The Game of Piles算法题超时优化：求双指针+前缀和高效解法

核心问题诊断 #

你当前的实现存在两个致命性能瓶颈：

• 展开数组会导致总长度达到O(ΣN)，当N普遍较大时总长度可能超过1e9，完全无法处理
• 逐元素模拟操作的时间复杂度也是O(ΣN)，无法适配大规模数据

核心优化逻辑 #

不需要展开数组，也不需要逐元素模拟操作，基于两个核心观察即可实现O(k)时间复杂度的解法：

• 连续相同值的块可以批量处理，每次操作直接计算整个块的总贡献，不需要拆分单个元素
• 所有操作本质是从左右两端向中间累积消耗：每次取左右两端当前值的最小值s，两端各减去s并将s传递到相邻内侧位置，等价于维护左右两侧的累计消耗值，批量移动左右指针指向的块，直到指针相遇或相邻。

优化实现代码（Python） #

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    k = int(data[idx])
    idx += 1
    v = []
    total = 0
    for _ in range(k):
        A = int(data[idx])
        N = int(data[idx+1])
        v.append((A, N))
        total += A * N
        idx += 2
    
    if k == 0:
        return
    l = 0
    r = k - 1
    l_remain = v[l][1]
    l_add = 0
    r_remain = v[r][1]
    r_add = 0
    
    while l < r:
        curr_l = v[l][0] + l_add
        curr_r = v[r][0] + r_add
        s = min(curr_l, curr_r)
        batch = min(l_remain, r_remain)
        
        l_remain -= batch
        r_remain -= batch
        
        if l_remain == 0:
            l += 1
            l_add = s
            l_remain = v[l][1] if l <= r else 0
        else:
            l_add += s
        
        if r_remain == 0:
            r -= 1
            r_add = s
            r_remain = v[r][1] if l <= r else 0
        else:
            r_add += s
    
    if l == r:
        if l_remain == 1:
            print(1)
            print(total)
        else:
            print(2)
            res1 = v[l][0] + r_add
            res2 = total - res1
            print(res1, res2)
    else:
        print(2)
        res1 = v[l][0] + l_add
        res2 = v[r][0] + r_add
        print(res1, res2)

if __name__ == "__main__":
    main()

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