流浪地球发动机

news/2024/9/19 18:37:53/ 标签: python

在这里插入图片描述

代码来自此处

python">if __name__ == '__main__':# 发动机的总个数, 计划手动启动的发动机总个数n, e = map(int, input().split())# 记录每个发动机的最终启动时刻, 初始化为极大值，方便后面取最早启动时刻launches = [1001] * nfor _ in range(e):# 发动机的手动启动时刻, 发动机的位置编号t, p = map(int, input().split())# p号发动机在t时刻手动启动launches[p] = t# 从编号 i 的发动机手动启动后, 关联启动到编号 jfor i in range(n):for j in range(n):# 内关联距离innerDis = abs(i - j)# 外关联距离outerDis = n - innerDis# 最短关联距离minDis = min(innerDis, outerDis)launches[j] = min(launches[j], launches[i] + minDis)maxT = 0  # 最晚启动时刻last = []  # 最晚启动的发动机编号集合for p in range(n):t = launches[p]  # 当前发动机启动时刻if t < maxT:  # 不是最晚启动的发动机continue# 更晚启动的时刻if t > maxT:maxT = tlast.clear()last.append(p)  # 记录该发动机编号last.sort()print(len(last))print(" ".join(map(str, last)))

感谢你的指正！让我们重新分析代码的执行流程，以确保我们正确理解最后被启动的发动机。

输入解析

输入为 8 2 和 0 2 0 6。
n = 8：表示有 8 个发动机，编号从 0 到 7。
e = 2：表示有 2 个手动启动的命令。
接下来的输入是：
- 0 2：表示在时刻 0 启动发动机 2。
- 0 6：表示在时刻 0 启动发动机 6。

代码执行流程

初始化：
```
python">launches = [1001] * n
```
- 创建一个列表 launches，长度为 8，初始值为 1001，表示所有发动机的启动时刻都未被启动。
```
launches = [1001, 1001, 1001, 1001, 1001, 1001, 1001, 1001]
```

记录手动启动：

python">for _ in range(e):t, p = map(int, input().split())launches[p] = t

第一次循环（_ = 0）：
- 输入 0 2，将发动机 2 的启动时刻更新为 0。
```
launches = [1001, 1001, 0, 1001, 1001, 1001, 1001, 1001]
```
第二次循环（_ = 1）：
- 输入 0 6，将发动机 6 的启动时刻更新为 0。
```
launches = [1001, 1001, 0, 1001, 1001, 1001, 0, 1001]
```

计算关联启动：
```
python">for i in range(n):for j in range(n):innerDis = abs(i - j)outerDis = n - innerDisminDis = min(innerDis, outerDis)launches[j] = min(launches[j], launches[i] + minDis)
```
内关联和外关联是指在环形结构中，两个相邻发动机之间的启动时延计算方式。由于发动机是环形排列的，因此在计算从一个发动机启动到另一个发动机的时间时，有两种可能的路径：内关联和外关联。

内关联（Inner Association）

定义：内关联是指在环形结构中，两个发动机之间的直接距离。
计算方式：如果发动机 i 和发动机 j 的编号分别为 i 和 j，则内关联的时间为 abs(i - j)，即它们之间的绝对差值。
示例：假设有 8 个发动机，编号从 0 到 7。
- 如果要从发动机 2 启动发动机 3，内关联时间为 abs(2 - 3) = 1。
- 如果要从发动机 6 启动发动机 7，内关联时间为 abs(6 - 7) = 1。

外关联（Outer Association）

定义：外关联是指在环形结构中，绕过环的另一侧到达目标发动机的距离。
计算方式：外关联的时间为 n - abs(i - j)，其中 n 是总的发动机数量。
示例：继续以上面的例子：
- 从发动机 2 启动发动机 3 的外关联时间为 8 - abs(2 - 3) = 8 - 1 = 7。
- 从发动机 6 启动发动机 7 的外关联时间为 8 - abs(6 - 7) = 8 - 1 = 7。

选择最小时间

在计算从发动机 i 启动到发动机 j 的时间时，我们需要选择内关联和外关联中的最小值：

python">minDis = min(innerDis, outerDis)

这确保了我们计算的是从一个发动机到另一个发动机的最短时间。

总结

内关联：直接相邻的距离，计算为 abs(i - j)。
外关联：绕过环的另一侧的距离，计算为 n - abs(i - j)。
在每次计算时，选择内关联和外关联中的最小值，以确保启动时间的最优化。
- 这个双重循环用于计算每个发动机的最早启动时刻。
- 例如：
  - 当 i = 2（发动机 2 启动时刻为 0）时：
    - j = 0：内关联距离为 abs(2 - 0) = 2，外关联距离为 8 - 2 = 6，最短距离为 2。
```
launches[0] = min(1001, 0 + 2) = 2
```
    - j = 1：内关联距离为 abs(2 - 1) = 1，外关联距离为 8 - 1 = 7，最短距离为 1。
```
launches[1] = min(1001, 0 + 1) = 1
```
    - j = 3：内关联距离为 abs(2 - 3) = 1，外关联距离为 8 - 1 = 7，最短距离为 1。
```
launches[3] = min(1001, 0 + 1) = 1
```
    - j = 4：内关联距离为 abs(2 - 4) = 2，外关联距离为 8 - 2 = 6，最短距离为 2。
```
launches[4] = min(1001, 0 + 2) = 2
```
    - j = 5：内关联距离为 abs(2 - 5) = 3，外关联距离为 8 - 3 = 5，最短距离为 3。
```
launches[5] = min(1001, 0 + 3) = 3
```
    - j = 6：内关联距离为 abs(2 - 6) = 4，外关联距离为 8 - 4 = 4，最短距离为 4。
```
launches[6] = min(0, 0 + 4) = 0
```
    - j = 7：内关联距离为 abs(2 - 7) = 5，外关联距离为 8 - 5 = 3，最短距离为 3。
```
launches[7] = min(1001, 0 + 3) = 3
```
- 当 i = 6（发动机 6 启动时刻为 0）时：
  - j = 0：内关联距离为 abs(6 - 0) = 6，外关联距离为 8 - 6 = 2，最短距离为 2。
```
launches[0] = min(2, 0 + 2) = 2
```
  - j = 1：内关联距离为 abs(6 - 1) = 5，外关联距离为 8 - 5 = 3，最短距离为 3。
```
launches[1] = min(1, 0 + 3) = 1
```
  - j = 2：内关联距离为 abs(6 - 2) = 4，外关联距离为 8 - 4 = 4，最短距离为 4。
```
launches[2] = min(0, 0 + 4) = 0
```
  - j = 3：内关联距离为 abs(6 - 3) = 3，外关联距离为 8 - 3 = 5，最短距离为 3。
```
launches[3] = min(1, 0 + 3) = 1
```
  - j = 4：内关联距离为 abs(6 - 4) = 2，外关联距离为 8 - 2 = 6，最短距离为 2。
```
launches[4] = min(2, 0 + 2) = 2
```
  - j = 5：内关联距离为 abs(6 - 5) = 1，外关联距离为 8 - 1 = 7，最短距离为 1。
```
launches[5] = min(3, 0 + 1) = 1
```
  - j = 7：内关联距离为 abs(6 - 7) = 1，外关联距离为 8 - 1 = 7，最短距离为 1。
```
launches[7] = min(3, 0 + 1) = 1
```
- 继续这个过程，直到所有发动机的启动时刻都被更新。最终，launches 列表将变为：
```
launches = [2, 1, 0, 1, 2, 1, 0, 1]
```

找出最后被启动的发动机：
```
python">maxT = 0
last = []
for p in range(n):t = launches[p]if t < maxT:continueif t > maxT:maxT = tlast.clear()last.append(p)
```
- 遍历 launches 列表，找出最后被启动的发动机：
  - p = 0：t = 2，更新 maxT = 2，last = [0]。
  - p = 1：t = 1，小于 maxT，跳过。
  - p = 2：t = 0，小于 maxT，跳过。
  - p = 3：t = 1，小于 maxT，跳过。
  - p = 4：t = 2，等于 maxT，last = [0, 4]。
  - p = 5：t = 1，小于 maxT，跳过。
  - p = 6：t = 0，小于 maxT，跳过。
  - p = 7：t = 1，小于 maxT，跳过。
输出结果：
```
python">last.sort()
print(len(last))
print(" ".join(map(str, last)))
```
- 对 last 列表进行排序，最终 last = [0, 4]。
- 输出最后被启动的发动机数量和编号：
```
2
0 4
```

这段代码的逻辑是用来找出最后被启动的发动机的编号。我们逐行分析这段代码的功能：

初始化：
```
python">maxT = 0  
last = []  
```
- maxT 用于跟踪当前找到的最大启动时刻。
- last 是一个列表，用于存储最后被启动的发动机的编号。
遍历所有发动机：
```
python">for p in range(n):  t = launches[p]  
```
- 通过 for 循环遍历所有发动机（从 0 到 n-1），p 是当前发动机的编号。
- t 是当前发动机的启动时刻，从 launches 列表中获取。
检查启动时刻：
```
python">if t < maxT:  continue  
```
- 如果当前发动机的启动时刻 t 小于 maxT，则跳过当前循环，继续检查下一个发动机。这意味着当前发动机不是最后被启动的发动机。
更新最大启动时刻：
```
python">if t > maxT:  maxT = t  last.clear()  
```
- 如果当前发动机的启动时刻 t 大于 maxT，则更新 maxT 为 t。
- 同时，清空 last 列表，因为找到了一个新的最大启动时刻，之前的发动机编号不再是最后被启动的。
记录发动机编号：
```
python">last.append(p)  
```
- 将当前发动机的编号 p 添加到 last 列表中。这意味着当前发动机是最后被启动的发动机之一。