【题目描述】假设有N盏灯N为不大于5000的正整数从1到N按顺序依次编号初始时全部处于开启状态;有M个人M为不大于N的正整数也从1到M依次编号。第一个人1号将灯全部关闭第二个人2号将编号为2的倍数的灯打开第三个人3号将编号为3的倍数的灯做相反处理即将打开的灯关闭将关闭的灯打开。依照编号递增顺序以后的人都和3号一样将凡是自己编号倍数的灯做相反处理。请问:当第M个人操作之后哪几盏灯是关闭的按从小到大输
【解题思路】 首先创建一个长度为N的数组lights,用来表示灯的状态。初始时,所有灯都是开启的,即lights[i]=1。
然后,从第一个人开始,依次遍历到第M个人。对于每个人,判断该人的编号是否是当前灯的倍数,如果是,则将该灯的状态取反(即0变为1,1变为0)。
最后,遍历数组lights,将状态为0的灯的编号输出,按从小到大的顺序,用逗号间隔。
【代码实现】
N, M = map(int, input().split())
lights = [1] * N
for i in range(1, M+1):
for j in range(i, N+1, i):
lights[j-1] = 1 - lights[j-1]
output = []
for i in range(N):
if lights[i] == 0:
output.append(str(i+1))
print(",".join(output))
【复杂度分析】 该算法的时间复杂度为O(N*M),空间复杂度为O(N)。其中,N为灯的数量,M为人的数量
原文地址: https://www.cveoy.top/t/topic/iAgM 著作权归作者所有。请勿转载和采集!