3385：破解锁的最少时间 II（★★）

Ian

2024-12-11 约 836 字预计阅读 2 分钟次阅读

力扣第 3385 题

题目

Bob 被困在了一个地窖里，他需要破解 n 个锁才能逃出地窖，每一个锁都需要一定的能量才能打开。每一个锁需要的能量存放在一个数组 strength 里，其中 strength[i] 表示打开第 i 个锁需要的能量。

Bob 有一把剑，它具备以下的特征：

一开始剑的能量为 0 。
剑的能量增加因子 X 一开始的值为 1 。
每分钟，剑的能量都会增加当前的 X 值。
打开第 i 把锁，剑的能量需要到达至少 strength[i] 。
打开一把锁以后，剑的能量会变回 0 ，X 的值会增加 1。

你的任务是打开所有 n 把锁并逃出地窖，请你求出需要的最少分钟数。

请你返回 Bob 打开所有 n 把锁需要的最少时间。

示例 1：

输入：strength = [3,4,1]

输出：4

解释：

时间	能量	X	操作	更新后的 X
0	0	1	什么也不做	1
1	1	1	打开第 3 把锁	2
2	2	2	什么也不做	2
3	4	2	打开第 2 把锁	3
4	3	3	打开第 1 把锁	3

无法用少于 4 分钟打开所有的锁，所以答案为 4 。

示例 2：

输入：strength = [2,5,4]

输出：6

解释：

时间	能量	X	操作	更新后的 X
0	0	1	什么也不做	1
1	1	1	什么也不做	1
2	2	1	打开第 1 把锁	2
3	2	2	什么也不做	2
4	4	2	打开第 3 把锁	3
5	3	3	什么也不做	3
6	6	3	打开第 2 把锁	4

无法用少于 6 分钟打开所有的锁，所以答案为 6。

提示：

n == strength.length
1 <= n <= 80
1 <= strength[i] <= 10⁶
n == strength.length

分析

看作 n 个锁和开锁顺序 [0,n-1] 之间的二分图，问题转为求二分图最大权完美匹配
可以用匈牙利算法，也可以用最小费用最大流

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64


# 最小费用最大流
class Dinic:
    def __init__(self,N):
        self.g = [[] for _ in range(N)]          # g 是图中每个 u 对应的 v 列表
        self.h = [inf]*N                        # h 是图中每个 u 离源点 s 的距离
        self.p = [0]*N              # p 是当前弧优化，跳过已增广的边
        self.vis = [0]*N
        self.N = N

    def add(self,u,v,c,w):                  # 顶点 u 和 v 连边，容量 c，费用 w
        self.g[u].append([v,len(self.g[v]),c,w])
        self.g[v].append([u,len(self.g[u])-1,0,-w])

    def spfa(self,s,t):
        self.h = [inf]*self.N
        self.h[s]=0
        Q, vis = deque([s]), {s}
        while Q:
            u = Q.popleft()
            vis.remove(u)
            for v,_,c,w in self.g[u]:
                if c>0 and self.h[u]+w<self.h[v]:
                    self.h[v] = self.h[u]+w
                    if v not in vis:
                        vis.add(v)
                        Q.append(v)
        return self.h[t]<inf

    def dfs(self,u,t,flow):
        if u==t:
            return flow
        self.vis[u] = 1
        res = 0
        for i in range(self.p[u],len(self.g[u])):
            v,j,c,w = self.g[u][i]
            if c>0 and not self.vis[v] and self.h[v]==self.h[u]+w:
                a = self.dfs(v,t,min(flow,c))
                flow -= a
                self.g[u][i][2]-=a
                self.g[v][j][2]+=a
                res += a
            self.p[u] += 1
        self.vis[u] = 0
        return res

    def cal(self,s,t):
        res = 0
        while self.spfa(s,t):
            res += self.dfs(s,t,inf)*self.h[t]
            self.p = [0]*self.N
        return res


class Solution:
    def findMinimumTime(self, strength: List[int]) -> int:
        n = len(strength)
        dinic = Dinic(n*2+2)
        s,t = n*2,n*2+1
        for i,a in enumerate(strength):
            dinic.add(s,i,1,0)
            dinic.add(i+n,t,1,0)
            for j in range(n):
                dinic.add(i,j+n,1,(a-1)//(j+1)+1)
        return dinic.cal(s,t)

8310 ms

目录

3385：破解锁的最少时间 II（★★）

题目

分析

解答