用 Python 编写程序，找出完成 K 项任务所需的最长时间
pythonserver side programmingprogramming更新于 2026/2/1 20:28:17
假设我们有一个任务矩阵，每行有 3 个值。我们还有另一个值 k。我们必须从任务中选择 k 行，将其称为 S，以使以下总和最小化并返回总和: (S[0, 0], S[1, 0], ...S[k - 1, 0]) 的最大值 + (S[0, 1], S[1, 1], ...S[k - 1, 1]) 的最大值 + (S[0, 2], S[1, 2], ...S[k - 1, 2]) 的最大值 我们也可以这样说:3 列中的每一列都会产生成本，并通过取 S 中该列的最大值来计算。空列表的最大值是 0。
因此，如果输入为任务 = [[2, 3, 3], [4, 5, 2], [4, 2, 3] ], k = 2，则输出将为 10，就像我们选择第一行和最后一行一样。总和将是 S = [[2,3,3],[4,2,3]] max(S[0,0], S[1,0]) = 4 + max(S[0,1], S[1,1]) = 3 + max(S[0,2], S[1,2]) = 3 = 10
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个函数 util() 。这将需要 B
- 对列表 B 进行排序
- yheap := 一个列表，其中每个 i 的范围为 0 到 K-1，且 -B[i, 1]
- heapify yheap
- ans := B[K - 1, 0] + (-yheap[0])
- 对于范围为 K 到 B 大小的 i，执行
- x := B[i, 0]
- 用 -B[i,1] 替换 yheap
- 设置 yheap 的大小与 K 相同
- y := -yheap[0]
- ans := ans 和 x + y 的最小值
- 返回 ans
- 从主方法执行以下操作−
- 如果 A 为空或 K 为 0，则
- 返回 0
- 对列表 A 进行排序
- B := 为每个 i 在 0 到 K-1 范围内创建一个对 [A[i, 1], A[i, 2]] 列表
- ans := A[K - 1, 0] + B 中每个 (y, z) 的 y 最大值 + B 中每个 (y, z) 的 z 最大值
- 对于 K 到 A 大小范围内的 i，执行
- 将 [A[i][1], A[i][2]] 插入 B
- ans = ans 和 A[i, 0] + util(B) 的最小值
- 返回 ans
让我们看看下面的实现以便更好地理解 −
示例
import heapq class Solution: def solve(self, A, K): if not A or not K: return 0 def util(B): B.sort() yheap = [-B[i][1] for i in range(K)] heapq.heapify(yheap) ans = B[K - 1][0] + (-yheap[0]) for i in range(K, len(B)): x = B[i][0] heapq.heappushpop(yheap, -B[i][1]) assert len(yheap) == K y = -yheap[0] ans = min(ans, x + y) return ans A.sort() B = [[A[i][1], A[i][2]] for i in range(K)] ans = A[K - 1][0] + max(y for y, z in B) + max(z for y, z in B) for i in range(K, len(A)): B.append([A[i][1], A[i][2]]) ans = min(ans, A[i][0] + util(B)) return ans ob = Solution() tasks = [ [2, 3, 3], [4, 5, 2], [4, 2, 3] ] k = 2 print(ob.solve(tasks, k))
输入
tasks = [ [2, 3, 3], [4, 5, 2], [4, 2, 3] ], k = 2
输出
10
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
