力扣第 2403 题
题目
你有一个整数数组 power，其中 power[i] 是第 i 个怪物的力量。
你从 0 点法力值开始，每天获取 gain 点法力值，最初 gain 等于 1。
每天，在获得 gain 点法力值后，如果你的法力值大于或等于怪物的力量，你就可以打败怪物。当你打败怪物时:
-
你的法力值会被重置为 0，并且
-
gain 的值增加 1。
返回打败所有怪物所需的 最少 天数。
示例 1:
输入: power = [3,1,4]
输出: 4
解释: 打败所有怪物的最佳方法是:
- 第 1 天: 获得 1 点法力值，现在总共拥有 1 点法力值。用尽所有法力值击杀第 2 个怪物。
- 第 2 天: 获得 2 点法力值，现在总共拥有 2 点法力值。
- 第 3 天: 获得 2 点法力值，现在总共拥有 4 点法力值。用尽所有法力值击杀第 3 个怪物。
- 第 4 天: 获得 3 点法力值，现在总共拥有 3 点法力值。 用尽所有法力值击杀第 1 个怪物。
可以证明，4 天是最少需要的天数。
示例 2:
输入: power = [1,1,4]
输出: 4
解释: 打败所有怪物的最佳方法是:
- 第 1 天: 获得 1 点法力值，现在总共拥有 1 点法力值。用尽所有法力值击杀第 1 个怪物。
- 第 2 天: 获得 2 点法力值，现在总共拥有 2 点法力值。用尽所有法力值击杀第 2 个怪物。
- 第 3 天: 获得 3 点法力值，现在总共拥有 3 点法力值。
- 第 4 天: 获得 3 点法力值，现在总共拥有 6 点法力值。用尽所有法力值击杀第 3 个怪物。
可以证明，4 天是最少需要的天数。
示例 3:
输入: power = [1,2,4,9]
输出: 6
解释: 打败所有怪物的最佳方法是:
- 第 1 天: 获得 1 点法力值，现在总共拥有 1 点法力值。用尽所有法力值击杀第 1 个怪物
- 第 2 天: 获得 2 点法力值，现在总共拥有 2 点法力值。用尽所有法力值击杀第 2 个怪物。
- 第 3 天: 获得 3 点法力值，现在总共拥有 3 点法力值。
- 第 4 天: 获得 3 点法力值，现在总共拥有 6 点法力值。
- 第 5 天: 获得 3 点法力值，现在总共拥有 9 点法力值。用尽所有法力值击杀第 4 个怪物。
- 第 6 天: 获得 4 点法力值，现在总共拥有 4 点法力值。用尽所有法力值击杀第 3 个怪物。
可以证明，6 天是最少需要的天数。
提示:
1 <= power.length <= 171 <= power[i] <= 109
相似问题：
分析
- 范围较小，可以用状压 dp
- 类似 3385，可以用最小费用最大流
解答
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
65
66
67
68
69
70
71
72
73
74
75
|
# 最小费用最大流，EK+dijkstra
class MCMF:
def __init__(self,N):
self.g = [[] for _ in range(N)] # g 是图中每个 u 对应的 v 列表
self.h = [inf]*N # h 是源点 s 到图中每个 u 的势能
self.d = [inf]*N # d 是图中每个 u 离源点 s 的最小费用距离
self.flow = [0]*N # EK 找增广路时，维护经过每个 u 的流量
self.fa = [-1]*N # EK 找增广路时，维护每个 u 的流量来源
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): # 预处理源点 s 到图中每个 u 的势能
self.h[s] = 0
dq = deque([s])
inq = [0]*self.N
inq[s] = 1
while dq:
u = dq.popleft()
inq[u] = 0
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 not inq[v]:
inq[v] = 1
dq.append(v)
def dij(self,s,t): # 找单位费用最小的增广路，每条边的费用经过势能转换
self.d = [inf]*self.N
self.d[s] = 0
self.flow[s] = inf
pq = [(0,s)]
while pq:
w,u = heappop(pq)
if w>self.d[u]:
continue
for v,j,c,w2 in self.g[u]:
nw = w+w2+self.h[u]-self.h[v]
if c>0 and nw<self.d[v]:
self.d[v] = nw
self.fa[v] = j
self.flow[v] = min(self.flow[u],c)
heappush(pq,(nw,v))
return self.d[t]<inf
def cal(self,s,t): # 重复增广，维护势能
res = 0
self.spfa(s)
while self.dij(s,t):
a = self.flow[t]
v = t
while v!=s:
j = self.fa[v]
u,i,_,_ = self.g[v][j]
self.g[u][i][2] -= a
self.g[v][j][2] += a
v = u
for u in range(self.N):
self.h[u] += self.d[u]
res += a*self.h[t]
return res
class Solution:
def minimumTime(self, power: List[int]) -> int:
n = len(power)
mcmf = MCMF(n*2+2)
s,t = n*2,n*2+1
for i,a in enumerate(power):
mcmf.add(s,i,1,0)
mcmf.add(i+n,t,1,0)
for j in range(n):
mcmf.add(i,j+n,1,(a-1)//(j+1)+1)
return mcmf.cal(s,t)
|
23 ms