数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：找出购买所有物品的最低成本
假设我们有N个物品，标记为0、1、2、…、N-1。然后，我们得到一个大小为S的二维列表sets。我们可以以sets[i,2]的价格购买第i个集合，并获得sets[i, 0]到sets[i, 1]之间的所有物品。此外，我们还有一个大小为N的列表removals，其中我们可以以removals[i]的价格丢弃第i个元素的一个实例。因此，我们必须找出精确购买从0到N-1（包含）每个元素的一个实例的最低成本，或者如果无法完成则结果为-1。
So, if the input is like sets = [ [0, 4, 4], [0, 5, 12], [2, 6, 9], [4, 8, 10] ]
removals = [2, 5, 4, 6, 8]，则输出将为4。
为了解决这个问题，我们将遵循以下步骤：
N := removals的大小
graph := 一个大小为(N + 1) x (N + 1)的新矩阵
对于每个s、e、w in sets，执行以下操作：
将[e+1, w]添加到graph[s]
对于每个索引i和物品r in removals，执行以下操作：
将[i, r]添加到graph[i + 1]
pq := 一个新的堆
dist := 一个新的映射
dist[0] := 0
当pq不为空时，执行以下操作：
d, e := 从堆pq中移除最小的项
如果dist[e] < d不为零，则：
继续下一次迭代
如果e与N相同，则：
返回d
对于每个nei, w in graph[e]，执行以下操作：
d2 := d + w
如果d2 < dist[nei]不为零，则：
dist[nei] := d2
将[d2, nei]添加到pq
返回-1
示例
让我们看看以下实现以更好地理解：
import heapq
from collections import defaultdict
class Solution:
def solve(self, sets, removals):
N = len(removals)
graph = [[] for _ in range(N + 1)]
for s, e, w in sets:
graph[s].append([e + 1, w])
for i, r in enumerate(removals):
graph[i + 1].append([i, r])
pq = [[0, 0]]
dist = defaultdict(lambda: float("inf"))
dist[0] = 0
while pq:
d, e = heapq.heappop(pq)
if dist[e] < d:
continue
if e == N:
return d
for nei, w in graph[e]:
d2 = d + w
if d2 < dist[nei]:
dist[nei] = d2
heapq.heappush(pq, [d2, nei])
return -1
ob = Solution()
print (ob.solve([
[0, 4, 4],
[0, 5, 12],
[2, 6, 9],
[4, 8, 10]
], [2, 5, 4, 6, 8]))输入
[[0, 4, 4], [0, 5, 12], [2, 6, 9], [4, 8, 10]], [2, 5, 4, 6, 8]
输出
4
更新于: 2020-12-23
277 次浏览
广告