力扣第 28 场双周赛第 4 题
题目
给你一个房屋数组houses 和一个整数 k ，其中 houses[i] 是第 i 栋房子在一条街上的位置，现需要在这条街上安排 k 个邮筒。
请你返回每栋房子与离它最近的邮筒之间的距离的 最小 总和。
答案保证在 32 位有符号整数范围以内。
示例 1：
输入：houses = [1,4,8,10,20], k = 3
输出：5
解释：将邮筒分别安放在位置 3， 9 和 20 处。
每个房子到最近邮筒的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。
示例 2：
输入：houses = [2,3,5,12,18], k = 2
输出：9
解释：将邮筒分别安放在位置 3 和 14 处。
每个房子到最近邮筒距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。
示例 3：
输入：houses = [7,4,6,1], k = 1
输出：8
示例 4：
输入：houses = [3,6,14,10], k = 4
输出：0
提示：
n == houses.length1 <= n <= 1001 <= houses[i] <= 10^41 <= k <= n- 数组
houses 中的整数互不相同。
分析
#1
- 令 f(i,j) 代表安排 i 个邮筒，houses[:j] 的最小距离和
- 遍历最后一个邮筒覆盖的房子范围 [a,j]，转为子问题 f(i-1,a-1)
- 计算一个邮筒覆盖区间 [a,b] 的最小和，将邮筒放在区间中位数即可，可以预处理前缀和，快速计算得到
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
cclass Solution:
def minDistance(self, houses: List[int], k: int) -> int:
def w(i,j):
l,r = (i+j)//2,(i+j+1)//2
return p[j]-p[r]-p[l]+p[i]+f[i]
A = houses
A.sort()
n = len(A)
p = [0]+list(accumulate(A))
f = [0]+[inf]*n
for _ in range(k):
nf = [inf]*(n+1)
for i in range(n+1):
for j in range(i):
nf[i] = min(nf[i],w(j,i))
f = nf
return f[-1]
|
399 ms
#2
- 区间代价函数 w 满足四边形不等式，可以利用决策单调性优化，详细见 四边形不等式优化
- 针对刚好 k 个区间问题，利用 opt(k−1,i)≤opt(k,i)≤opt(k,i+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
|
class Solution:
def minDistance(self, houses: List[int], k: int) -> int:
def w(i,j):
l,r = (i+j)//2,(i+j+1)//2
return p[j]-p[r]-p[l]+p[i]+f[i]
A = houses
A.sort()
n = len(A)
p = [0]+list(accumulate(A))
f = [0]+[inf]*n
pt = [0]*(n+1)
for _ in range(k):
nf = [inf]*(n+1)
npt = [n]*(n+2)
for i in range(n,-1,-1):
for j in range(pt[i],npt[i+1]+1):
tmp = w(j,i)
if tmp<nf[i]:
nf[i] = tmp
npt[i] = j
f = nf
pt = npt
return f[-1]
|
35 ms
附加
- 这类问题还可以结合 wqs 二分进一步优化
- 证明见 四边形不等式优化
- 此时采用通用的简化 LARSCH 算法 ，当 𝑤(𝑗,𝑖) 需要动态计算，或者只支持移动访问时都能处理
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
|
class Solution:
def minDistance(self, houses: List[int], k: int) -> int:
def cal(x): # 选一个的额外代价是x时，最大收益s及对应最小次数c
def w(i,j):
l,r = (i+j)//2,(i+j+1)//2
a,c = f[i]
return (p[j]-p[r]-p[l]+p[i]+a+x,c+1)
def update(i,j):
tmp = w(i,j)
if tmp<f[j]:
f[j] = tmp
pt[j] = i
# 递归求解区间 (l, r] 内的问题
def dfs(l,r):
mid = (l+r+1)//2
for j in range(pt[l],pt[r]+1):
update(j,mid)
if mid<r:
dfs(l,mid)
for j in range(l+1,mid+1):
update(j,r)
if mid>l:
dfs(mid,r)
f = [(inf,0) for _ in range(n+1)]
f[0] = (0,0)
pt = [0]*(n+1)
update(0,0)
update(0,n)
dfs(0,n)
return f[-1][0],f[-1][1]
A = houses
A.sort()
n = len(A)
p = [0]+list(accumulate(A))
l,r = 0,p[-1]
res = 0
while l<=r:
mid = (l+r)//2
s,c = cal(mid)
if c<=k:
res = s-k*mid
if c==k:
break
r = mid-1
else:
l = mid+1
return res
|
90 ms