为什么我在2018年《再次拯救世界》中的回答是错误的？

Question

这里提出了这个问题：https://codingcompetitions.withgoogle.com/codejam/round/00000000000000cb/0000000000007966

一个外星机器人正在威胁宇宙，它使用的光束将摧毁所有的知识。我们必须阻止它

幸运的是，我们了解机器人的工作原理。它从一个强度为1的梁开始，它将运行一个由一系列指令组成的程序，这些指令将按从左到右的顺序一次执行一个。每个指令属于以下两种类型之一：

C（表示“电荷”）：梁的强度加倍。 S（代表“射出”）：射出光束，造成与光束当前强度相等的伤害。 例如，如果机器人的程序是SCCSSC，则当程序运行时，机器人将执行以下操作：

射出光束，造成1点伤害。 对光束充电，使光束强度加倍至2。 对光束充电，使光束强度加倍至4。 射出光束，造成4点伤害。 射出光束，造成4点伤害。 对光束充电，将光束强度增加到8。 在这种情况下，该程序将总共造成9点伤害

宇宙中最顶尖的算法学家已经开发出一种防护罩，可以承受最大的D级伤害。但是机器人当前的程序在运行时可能会造成更大的破坏

宇宙主席自愿飞上太空，在机器人运行之前破解机器人的程序。总统可以破解（机器人没有注意到）的唯一方法是交换两条相邻的指令。例如，总统可以通过交换第三条和第四条指令使其成为SCSC来破解上述程序一次。这将使总伤害减少到7点。然后，例如，总统可以再次破解该程序，使其成为SCSSCC，将伤害降低到5，等等

为了防止机器人变得太可疑，总统不想黑客攻击太多次。如果有可能的话，确保程序造成的总伤害不超过D的最小黑客数量是多少

输入 输入的第一行给出了测试用例的数量，然后是T.T测试用例。每一行包含一个整数D和一个字符串P：我们的防护罩能够承受的最大总伤害，以及机器人的程序

输出 对于每个测试用例，输出一行包含用例#x:y，其中x是测试用例编号（从1开始），y是完成目标所需的最小破解次数，如果不可能，则为不可能

---

我实现了以下逻辑： -首先计算船的损坏程度。 -S在结束时具有最大的价值，因此掉期应该从结束时开始，并继续到列表的开始。 -最后的C变得没用了，所以我把它从列表中弹出，这样它就不会再次迭代了。 -为了简化O（）的复杂性，我决定每次交换时从sum中减去S的最后一个值。 测试结果似乎是对的，但系统的法官说：答案错了。 你能帮我找出错误吗？

---

（我只知道如何使用Python3中的列表和字典，我是解决这些问题的绝对初学者） 我的代码如下：

for case in range(1,T):
    D, B = input().split()
    D = int(D)
    Blist =[]
    [Blist.append(i) for i in B]

    def beamDamage(Blist):
        theSum=0
        intS=1
        Ccount = 0
        for i in Blist:
            if i == 'S':
                theSum = theSum + intS
            if i == 'C':
                Ccount = Ccount +1
                intS = intS*2
        return theSum

    def swap(Blist):
        temp=''
        for i in range(0,len(Blist)):
            if Blist[len(Blist)- 1] == 'C':
                Blist.pop()
            if (Blist[len(Blist)- i - 1]) == 'C' and (Blist[len(Blist)- i] == 'S'):
                temp = Blist[len(Blist)- i - 1]  # C 
                Blist[len(Blist)- i - 1] = 'S'
                Blist[len(Blist)- i] = temp
                return Blist


    bd = beamDamage(Blist)
    y = 0

    if 'C' not in B:
        if beamDamage(Blist) > D:
            print("Case #{}: IMPOSSIBLE".format(case))
        else:
            print("Case #{}: 0".format(case))
    else:
        while bd > D:  
            swap(Blist)
            pwr=0
            for ch in Blist:
                if ch == 'C':
                    pwr=pwr+1
            bd = bd - 2**(pwr-1)
            y+=1
        print("Case #{}: {}".format(case, y))  

Answer 1

我不会给你一个完整的解决方案，但这里有一个问题：

如果您的输入是一系列的“S”后跟一个或多个“C”（如“SSSSC”），并且计算出的损伤高于要求的损伤，您将清楚地看到结果是错误的。这应该是不可能的

失败的原因是if 'C' not in B:中的条件将不适用，因此循环将启动（实际上不应该启动）。因此pwr保持为零，使用2**-1进行计算，这将产生一个非整数值

解决方案是，即使在执行if测试之前，也要从一开始就终止C个字符来修剪列表

其次，我不认为用两种不同的方法计算损失有什么好处。一方面，您有beamDamage，还有内联循环，其作用大致相同（不是更快）

最后，即使你做对了，我怀疑你的代码可能会超时，因为它没有有效地完成工作。考虑以增量方式跟踪损失，而无需再次查看整个列表

一旦有了改进，您可能仍然需要进一步调整性能。在这种情况下，想想你会得到什么样的伤害减免，你会立即将一个“C”移到列表的最后。如果这一减少仍然没有使伤害低于目标，你可以一次减少伤害（但仍然正确计算步数）