为何在HackerEarth平台运行Python代码出现MLE（内存超限）？

问题描述 #

现有一段求解巫师考试最少法力值的Python代码，在处理超大输入用例时触发**内存超限（MLE）**错误，相同逻辑的C++代码可正常运行，平台内存限制为256MB。

原代码 #

t = int(input())

for i in range(t):
    x,l,n = map(int, input().split())
    for xi in range(x,-1,-1):
        if xi*(2**(n-1))<=l:
            print(x-xi)
            break

触发错误的测试用例 #

1
1000000000000000000 0 1000000000000000000

问题背景 #

Kate是一名巫师，需进入魔法房间N次：

• 初始房间内有X件魔法物品
• 每次进入前可销毁物品，每件消耗1点法力值
• 每次进入后物品数量翻倍
• 物品数量超过L则无法进入房间
  求通过考试所需的最少法力值，需支持多组测试用例。

错误原因 #

Python的range(x,-1,-1)在x为1e18这种超大数值时，会尝试生成一个包含1e18+1个元素的序列。Python整数本身占用内存远大于C基本类型，如此庞大的序列会直接耗尽256MB内存，触发MLE。而C的for循环是逐次迭代判断，不会预先生成整个序列，因此无内存问题。

修复方案 #

无需遍历所有可能的xi，通过数学计算直接得到最大可保留的物品数xi_max，从而算出最少法力值：

1. 当进入次数n=1时，最大可保留物品数为min(x, l)
2. 当n>1时，计算2^(n-1)：若该值超过l，则必须销毁所有物品（xi_max=0）；否则xi_max=min(x, l // 2^(n-1))
3. 为避免计算超大指数导致性能问题，可提前终止指数计算

优化后代码 #

t = int(input())
for _ in range(t):
    x, l, n = map(int, input().split())
    if n == 1:
        xi_max = min(x, l)
    else:
        factor = 1
        # 计算2^(n-1)，中途若超过l则停止
        for _ in range(n-1):
            if factor > l // 2:
                factor = l + 1
                break
            factor *= 2
        xi_max = 0 if factor > l else min(x, l // factor)
    print(x - xi_max)

该代码仅使用固定内存，不会生成超大序列，同时避免了大指数计算的性能损耗，可正常处理所有测试用例。

内容的提问来源于stack exchange，提问作者Deekshith Ranga Babu Tirumala