OD E卷 - 实现【流浪地球】

题目

在赤道上均匀部署N个转向发动机，编号为0 ~ N - 1：

• 默认 为未启动状态，启动方式为手动启动、关联启动；
• 如果在时刻1一个发动机被启动，在时刻2 与之相邻的两个发动机就会被关联启动；
• 若准备启动某个发动机时，它已经启动，则什么都不用做；
• 发动机0与N-1是相邻的；

输入描述：
第一行输入N E, N为发动机总数，E表示手动启动的发动机总个数；
N, E 在【1， 1000】之间，E<=N;

后续E行，每行输入 T P，分别表示手动启动的时刻，启动发动机编号；
T，P均在【0，N】之间；

输出描述:
第一行为一个数字N，表示最后被启动的发动机个数；
第二行为N个发送机的编号，从小到大排序，以空格分隔；

示例1：
输入：
8 2
0 2
0 6
输出：
2
0 4

示例2：
输入：
8 2
0 1
1 7
输出：
2
4 5

解题代码

# 第一行输入N E
nums = [int(x) for x in input().split(" ")]
# 总发动机数
count = nums[0]
# 数组保存所有的节点，数组值，代表对应位置启动时间
engines = [-1 for i in range(count)]  # -1表示未激活# 手动启动个数
start_cnt = nums[1]
min_time = float("inf")
for i in range(start_cnt):  # 行数nums1 = [int(x) for x in input().split(" ")]# 更新对应发动机的启动时间engines[nums1[1]] = nums1[0]# 当前时刻min_time = min(min_time, nums1[0])def activate(index, time, count):# index当前已经启动的位置编号# time为当前时刻# count 为发动机总数global engines# 更新当前位置左右的节点left = index - 1if index == 0:left = count - 1right = index + 1if index == count - 1:right = 0# 激活if engines[left] == -1:engines[left] = timeif engines[right] == -1:engines[right] = timedef find(start):  # start 为起始时间 0global enginesflag = Truewhile flag:for i in range(len(engines)):if engines[i] == start:  # 从开始位置向两边激活activate(i, start + 1, len(engines))start += 1active_cnt = 0  # 已激活的数量for i in range(len(engines)):if engines[i] != -1:active_cnt += 1# 全部激活，则停止if active_cnt == len(engines):flag = False# 最后激活的时间节点max_time = engines[0]for i in range(len(engines)):if engines[i] > max_time:max_time = engines[i]count = 0result = ""for i in range(len(engines)):if max_time == engines[i]:result += str(i) + " "count += 1# 输出最后激活的总数 及编号print(count)print(result[:-1])find(min_time)