86.多零件流水线优化标题|Marscode AI刷题

1.标题

标题形貌

小C、小U、小R是工厂里的三个工人，他们相互协同制作零件。零件的制作包罗三种工序："加工"、"质检"、"收尾"，分别由小C、小U、小R负责。每个零件必要多次举行"加工"和"质检"工序，但只必要举行一次"收尾"工序。每次"加工"完成后，必要举行对应的"质检"，只有当质检合格后，才可以开始下一次"加工"。当全部的"加工"和"质检"工序完成后，举行一次"收尾"工序，如许零件制作就算完成了。
小C、小U、小R的工作方式原来非常机器化，他们只能按照既定序次一个工序一个工序地完成一个零件，比如对于一个零件的工序"加工1、质检1、加工2、质检2、收尾"，他们会按序次逐一完成各自的任务。
老板以为如许太低效了，于是订定了新的加工方式：小C、小U、小R之间不应该相互称候，当他们因工序等待而被壅闭时，可以直接开始新零件的加工。但是每个工序在举行中不能被打断，必须连贯地完成。
比方，有5个零件，每个零件有7道工序，分别耗时如下：
零件一：10, 10, 10, 10, 10, 10, 20
零件二：10, 10, 10, 10, 10, 10, 20
零件三：10, 10, 10, 10, 10, 10, 20
零件四：10, 10, 10, 10, 10, 10, 20
零件五：10, 10, 10, 10, 10, 10, 20
（每一行的7个数字分别表现"加工1"，"质检1"，"加工2"，"质检2"，"加工3"，"质检3"，"收尾"的耗时）
假设零件按照5、4、3、2、1的优先级开始制作，优化后的工序流程中，小C、小U、小R会更加繁忙，制止空闲。
现在给你n个零件及每个零件的工序耗时，问在颠末流程优化后，全部零件加工必要耗费的总时间是多少？

---

测试样例

样例1：
输入：n = 5, parts = [[7, 10, 10, 10, 10, 10, 10, 20], [7, 10, 10, 10, 10, 10, 10, 20], [7, 10, 10, 10, 10, 10, 10, 20], [7, 10, 10, 10, 10, 10, 10, 20], [7, 10, 10, 10, 10, 10, 10, 20]]
输出：200
样例2：
输入：n = 3, parts = [[5, 10, 5, 10, 5, 10], [5, 2, 4, 6, 2, 10], [3, 10, 2, 5]]
输出：57
样例3：
输入：n = 4, parts = [[5, 7, 5, 8, 5, 7], [3, 5, 2, 7], [5, 3, 6, 4, 3, 6], [7, 7, 3, 4, 7, 3, 5, 6]]
输出：60
2.思绪

1.数据结构选择

• 每个零件的工序时间被存储在 parts 数组中，此中每个零件有一个列表，第一个元素表现该零件的工序数，后续元素表现每个工序的耗时。
  
• flag 数组用来标志每个工序是否完成。我们用 0 和 1 来表现工序是否已经开始或完成。
  
• m1, m2, m3 分别表现“加工”、“质检”和“收尾”阶段的竣事时间。
  

2. 调理模仿流程

• 优先队列（堆）：我们利用一个优先队列（堆）来处置处罚每个工序的时间。每次弹出堆中的最早时间，处置处罚该时间点的工序，并安排下一个工序。
  
• 标志数组：flag[j] 表现第 i 个零件的第 j 个工序是否已完成。初始时全部零件的第一个工序都开始举行。
  

3. 工序实行序次

• 加工工序（m1）：假如当前时间已颠末了某个零件的加工工序，我们会将其加工工序标志为完成，并将下一个加工工序安排进入队列。
  
• 质检工序（m2）：假如当前时间已颠末了某个零件的质检工序，我们将安排下一个质检工序。
  
• 收尾工序（m3）：当某个零件的末了一个工序完成时，我们安排收尾工序进入队列。
  

4. 竣事条件

当全部零件的工序都完成时，sum_jobs 会变为 0，意味着全部的工序已经完成，终极时间 time 就是任务竣事的时间。
3.代码

2. import heapq
3. def solution(n, parts):
4.     # Please write your code here
5.     # 验证输入的零件数量是否与工序列表的长度一致
6.     assert n == len(parts)
7.    
8.     # 初始化标记数组flag，用来表示每个工序是否已完成
9.     flag = [[0 for _ in range(len(part))] for part in parts]
10.    
11.     # b是每个零件的工序数量（即每个零件的加工数量）
12.     b = [part[0] for part in parts]
13.    
14.     # sum_jobs记录尚未完成的工序数量
15.     sum_jobs = sum(b)
16.    
17.     # a是每个零件各个工序的耗时数据，去掉了第一个工序数量的元素
18.     a = [part[1:] for part in parts]
19.    
20.     # 初始化第一个工序的标记，表示所有零件的第一个工序已经开始
21.     for i in range(n):
22.         flag[i][0] = 1
23.    
24.     # 初始时间为0
25.     time = 0
26.     # m1, m2, m3表示分别进行“加工”、“质检”和“收尾”的结束时间
27.     m1, m2, m3 = 0, 0, 0
28.     # last1i, last1j表示上一轮“加工”工序的零件索引和工序索引
29.     last1i, last1j = -1, -1
30.     # last2i, last2j表示上一轮“质检”工序的零件索引和工序索引
31.     last2i, last2j = -1, -1
32.     # last3i表示上一轮“收尾”工序的零件索引
33.     last3i = -1
35.     # 使用优先队列（堆）来处理工序的执行时间
36.     q = []
37.     heapq.heappush(q, 0) # 将0（初始时间）加入队列
39.     # 当还有未完成的工序时，持续处理
40.     while sum_jobs > 0:
41.         time = heapq.heappop(q)
43.         # 处理所有在相同时间点需要处理的工序
44.         while q and q[0] == time:
45.             heapq.heappop(q)
47.         # 如果当前时间为m3（“收尾”时间），且有待收尾的工序，则减少未完成工序数量
48.         if time == m3 and last3i != -1:
49.             sum_jobs -= 1
51.         # 如果当前时间为m2（“质检”时间），且质检工序未完成，则开始下一个质检工序
52.         if time == m2 and last2i != -1 and last2j != -1:
53.             flag[last2i][last2j + 1] = 1 # 标记该零件的质检工序已完成
54.             sum_jobs -= 1 # 完成一个工序，减少未完成的工序数量
56.         # 如果当前时间大于等于m1（“加工”时间），尝试安排新的加工工序
57.         if time >= m1:
58.             if time == m1 and last1i != -1 and last1j != -1:
59.                 flag[last1i][last1j + 1] = 1 # 标记加工工序已完成
60.                 sum_jobs -= 1 # 完成一个工序，减少未完成的工序数量
61.             # 查找下一个可以进行的加工工序
62.             found = False
63.             for i in range(n):
64.                 for j in range(0, b[i], 2): # 偶数索引表示加工工序
65.                     if flag[i][j] == 1 and j != b[i] - 1: # 检查工序是否已完成
66.                         temi, temj = i, j
67.                         flag[temi][temj] = 0 # 标记该工序已开始
68.                         m1 = time + a[temi][temj] # 计算新的加工结束时间
69.                         last1i, last1j = temi, temj # 记录最新加工工序的位置
70.                         heapq.heappush(q, m1) # 将加工结束时间加入队列
71.                         found = True
72.                         break
73.                 if found:
74.                     break
75.         
76.         # 如果当前时间大于等于m2（“质检”时间），尝试安排新的质检工序
77.         if time >= m2:
78.             found = False
79.             for i in range(n):
80.                 for j in range(1, b[i], 2):
81.                     if flag[i][j] == 1:
82.                         temi, temj = i, j
83.                         flag[temi][temj] = 0
84.                         m2 = time + a[temi][temj]
85.                         last2i, last2j = temi, temj
86.                         heapq.heappush(q, m2)
87.                         found = True
88.                         break
89.                 if found:
90.                     break
91.         
92.         # 如果当前时间大于等于m3（“收尾”时间），开始安排收尾工序
93.         if time >= m3:
94.             for i in range(n):
95.                 if flag[i][b[i] - 1] == 1:
96.                     temi = i
97.                     flag[temi][b[temi] - 1] = 0 # 标记收尾工序已开始
98.                     m3 = time + a[temi][b[temi] - 1]
99.                     last3i = temi
100.                     heapq.heappush(q, m3)
101.                     break
103.     return time
105. if __name__ == "__main__":
106.     #  You can add more test cases here
107.     parts1 = [[7, 10, 10, 10, 10, 10, 10, 20],
108.               [7, 10, 10, 10, 10, 10, 10, 20],
109.               [7, 10, 10, 10, 10, 10, 10, 20],
110.               [7, 10, 10, 10, 10, 10, 10, 20],
111.               [7, 10, 10, 10, 10, 10, 10, 20]]
112.     parts2 = [[5, 10, 5, 10, 5, 10],
113.               [5, 2, 4, 6, 2, 10],
114.               [3, 10, 2, 5]]
115.     print(solution(5, parts1) == 200)
116.     print(solution(3, parts2) == 57)

复制代码

heapq 是 Python 内置的一个模块，用于实现堆（heap）数据结构，堆是一种二叉树结构，满足“堆序性子”，可以高效地获取最小（或最大）元素。heapq 模块实现的是一个最小堆（min-heap），即堆顶元素总是最小的。
紧张功能

• 堆的插入和删除：通过 heapq 提供的函数，可以轻松地维护一个堆，支持插入、删除、获取最小元素等利用。
  
• 优先队列：由于堆可以高效地获取最小元素，以是它通常用于实现优先队列（priority queue），比方在你提供的代码中，堆用于存储和处置处罚差别时间点的工序。
  

常用函数

•         heapq.heappush(heap, item)
          向堆中插入一个元素，并保持堆的性子。
  
  
  
  • heap：堆数据结构（列表）
    
  • item：要插入的元素
    
  3. import heapq
  4. heap = [1, 3, 5, 7, 9, 2]
  5. heapq.heappush(heap, 4)
  6. print(heap)  # 输出 [1, 3, 2, 7, 9, 5, 4]

  复制代码
  
  
•         heapq.heappop(heap)
          从堆中弹出并返回最小的元素，并重新保持堆的性子。
  
  
  
  • 返回堆中的最小元素，且移除该元素。
    
  3. import heapq
  4. heap = [1, 3, 5, 7, 9, 2]
  5. print(heapq.heappop(heap))  # 输出 1
  6. print(heap)  # 输出 [2, 3, 5, 7, 9]

  复制代码
  
  
•         heapq.heappushpop(heap, item)
          向堆中插入元素，然后立即弹出并返回堆中最小的元素。这个利用比先插入然后再弹出要高效。
  
  3. import heapq
  4. heap = [1, 3, 5, 7, 9, 2]
  5. print(heapq.heappushpop(heap, 4))  # 输出 1，4 被插入后 1 被弹出
  6. print(heap)  # 输出 [2, 3, 4, 7, 9, 5]

  复制代码
•         heapq.heapify(iterable)
          将一个可迭代对象转换成堆。
  
  
  
  • iterable：可以是列表、元组等，转化为堆结构。
    
  3. import heapq
  4. heap = [5, 7, 9, 1, 3, 2]
  5. heapq.heapify(heap)
  6. print(heap)  # 输出 [1, 3, 2, 7, 5, 9]

  复制代码
  
  
•         heapq.nlargest(n, iterable)
          获取 iterable 中最大的 n 个元素。
  
  
  
  • n：必要返回的元素个数
    
  • iterable：可以是任何可迭代对象
    
  3. import heapq
  4. nums = [1, 3, 5, 7, 9, 2]
  5. print(heapq.nlargest(3, nums))  # 输出 [9, 7, 5]

  复制代码
  
  
•         heapq.nsmallest(n, iterable)
          获取 iterable 中最小的 n 个元素。
  
  
  
  • n：必要返回的元素个数
    
  • iterable：可以是任何可迭代对象
    
  3. import heapq
  4. nums = [1, 3, 5, 7, 9, 2]
  5. print(heapq.nsmallest(3, nums))  # 输出 [1, 2, 3]

  复制代码