Photoshoot（2020jan铜牌）

Question

第1题 面包人灭灯泡 查看测评数据信息
一次面包人做的面包因为灯泡太热而全部烤糊了，面包人十分的伤心。他觉得这一切都是灯泡的错（明明就是你把电灯泡乱放就去秀恩爱），所以，面包人发誓要大闹电灯泡工厂。

电灯泡工厂总共有n个位置，每个位置都有一个电灯泡，每个电灯泡都有两种状态。0表示关，1表示开。面包人觉得这么多电灯泡聚在一起能产生的热量能毁灭世界。面包人为了保卫世界的和平，于是他决定要关掉电灯泡。

当面包人把电灯泡全部关掉的时候，电灯泡工厂就会因为没有热能造电而失去作用，也就是说当电灯泡全部关掉的时候面包人就拯救了世界。

因为面包人是面包人，所以他有三只手，而他每次只能也必须改变三个电灯泡的状态。

然而，电源每秒能产生1xea的热量，当热量达到k时，世界就会砰的一声毁灭了。

那么，现在问题来了（挖掘机到底哪家强？）面包人能不能拯救面包球，如果能，输出最小的时间，否则输出‘lamp kill the world!’不加引号。（当然是蓝翔）

【注意】：所有数据至少包含3个0。

输入格式
输入一行n,k，n为电灯泡工厂的位置的个数，k为面包球所能承受的热量。

一行数字，表示第i个数字表示第i电灯泡的状态，0表示关，1表示开。

输出格式
输出面包人拯救面包球用的时间，如果世界毁灭了，输出’lamp kill the world!’（不加引号）。

输入/输出例子1
输入：

样例一：

5 1

0 1 1 0 0

样例二：

5 3

0 1 1 0 0

输出：

样例一：

lamp kill the world!

样例二：

2

样例解释
【样例解释】
样例二：
Time1：0 1 0 1 1 xea:1（time1）
Time2：0 0 0 0 0 xea:2 （time2）

【数据范围】

30%的数据：0<=k<=n<=100
60%的数据：0<=k<=n<=10000
100%的数据：0<=k<=n<=1000000
c++语言

Answer 1

【以下回答由 GPT 生成】

由于面包人每次可以改变三个电灯泡的状态，所以可以利用这个特性来尽量快速地将所有电灯泡关掉。以下是解决该问题的具体步骤：

1. 首先，读取输入的n和k，并将其分别赋值给变量num_of_lamps和heat_limit。将输入的电灯泡状态保存在一个列表中，命名为lamp_status。

num_of_lamps, heat_limit = map(int, input().split())
lamp_status = list(map(int, input().split()))

1. 创建一个变量time，用于记录面包人拯救面包球所用的时间，初始值设为0。

time = 0

1. 创建一个变量heat，用于记录当前热量的累积值，初始值设为0。

heat = 0

1. 创建一个循环，用于尝试关掉电灯泡并更新热量的累积值。循环条件是heat小于热量限制k且至少还有一个电灯泡是开启的。

while heat < heat_limit and 1 in lamp_status:

1. 在循环内部，遍历电灯泡列表lamp_status，找到连续三个开启的电灯泡。

for i in range(len(lamp_status) - 2):
    if lamp_status[i] == 1 and lamp_status[i + 1] == 1 and lamp_status[i + 2] == 1:
        # 关掉这三个电灯泡
        lamp_status[i] = 0
        lamp_status[i + 1] = 0
        lamp_status[i + 2] = 0
        # 更新热量累积值
        heat += 3
        # 更新时间
        time += 1
        # 跳出当前循环，重新开始查找下一个连续三个开启的电灯泡
        break

1. 当循环结束时，判断是否成功将所有电灯泡关掉。如果成功关掉了所有电灯泡，则输出拯救面包球所用的时间time；否则，输出'lamp kill the world!'。

if 1 not in lamp_status:
    print(time)
else:
    print('lamp kill the world!')

完整的代码如下：

num_of_lamps, heat_limit = map(int, input().split())
lamp_status = list(map(int, input().split()))

time = 0
heat = 0

while heat < heat_limit and 1 in lamp_status:
    for i in range(len(lamp_status) - 2):
        if lamp_status[i] == 1 and lamp_status[i + 1] == 1 and lamp_status[i + 2] == 1:
            lamp_status[i] = 0
            lamp_status[i + 1] = 0
            lamp_status[i + 2] = 0
            heat += 3
            time += 1
            break

if 1 not in lamp_status:
    print(time)
else:
    print('lamp kill the world!')

该代码的时间复杂度为O(n)，其中n为电灯泡的个数。

【相关推荐】

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/660764
• 除此之外, 这篇博客: Educational Codeforces Round 102 (Rated for Div. 2)中的 思路：首先考虑在没有删除的情况下，一系列操作过程中，能变成多少不同的值。x初始为0，随着+±-的变化，会来回反复横跳，那么两个关键点就是最大值和最小值，这说明从最大值到最小值之间的数字，都是在操作过程中出现。所以只需要考虑一个区间内的操作产生的最大最小值。但是题目要删掉，中间一段，剩下两段，也就是要把两段合并起来。画个图其实更好理解。红色的是所有的操作，绿色的是要删除的操作，第二个曲线就是合并之后的x值变化曲线。由图可知。后面那部分合并过来之后，起点就是前面那部分的终点！这就是关键点。然后前面那部分的区间的最大最小值和当前值都很好维护。难的是后面那部分怎么维护。后面那部分，从后往前维护，每到一个点，都认为这个点是零点，然后计算最大值最小值。因为是反着来，可以发现操作曲线是一个与 原操作 关于x轴对称的曲线，所以最大值就是最小值，最小值就是最大值。然后最小值就是 当前点到最小值的距离，最大值就是 当前点到最大值的距离。之所以算距离，是因为，永远认为当前点是0点。所以 距离 才是真正的最大最小值。 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^