【Leetcode】1478. Allocate Mailboxes

题目地址：

https://leetcode.com/problems/allocate-mailboxes/description/

给定一个长$n$的数组$h$，表示$n$个房子的坐标，题目保证坐标都是正整数。再给定一个小于等于$n$的正整数$m$，允许在数轴上放$m$个邮箱，设$g[i]$为下标为$i$的房子与与其最近的邮箱的距离，问${\sum }_{i=1}^{n}g[i]$可以取得的最小值。

设$h$的前缀和数组为$p$，先预处理出二维数组$c[i][j]$，含义是如果$h[i:j]$中的房子都由一个邮箱管辖，那么$c[i][j]$即为${\sum }_{t=i}^{j}g[t]$能取得的最小值。那么显然邮箱应该取在中位数的位置，即$h[\lfloor \frac{i+j}{2}\rfloor ]$，设$l=\lfloor \frac{i+j}{2}\rfloor$，所以：$$\begin{gathered} c[i][j]=\sum _{t=i}^j|h[t]-h[l]|= \\ \sum _{t=i}^l(h[l]-h[t])+\sum _{t=l+1}^j(h[t]-h[l]) \\ =(2l-i-j+1)h[l]-(p[l+1]-p[i])+(p[j+1]-p[l+1]) \\ =(2l-i-j+1)h[l]+p[i]+p[j+1]-2p[l+1] \end{gathered}$$接着，设$f[i][j]$是只考虑$h[0:i]$这些房子，且开不多于$j$个邮箱的情况下，能取到的最小总距离。那么所有的方案可以按照最右边那个邮箱的管辖范围来分类，如果其管辖了$[0:i]$，则可以用$c[0][i]$来更新$f[i][j]$；如果其管辖了$[k:i],k>0$，则可以用$c[k][i]+f[k-1][j-1]$来更新$f[i][j]$。最后返回$f[n-1][m]$即可。代码如下：

class Solution {
 public:
  int minDistance(vector<int>& h, int m) {
    sort(h.begin(), h.end());
    int n = h.size();
    int f[n][m + 1], cost[n][n], p[n + 1];
    memset(f, 0, sizeof f);
    p[0] = 0;
    for (int i = 0; i < n; i++) p[i + 1] = h[i] + p[i];
    for (int i = 0; i < n; i++)
      for (int j = i; j < n; j++) {
        int mid = (i + j) / 2;
        cost[i][j] =
            (i + j & 1 ^ 1) * h[mid] + p[i] + p[j + 1] - 2 * p[mid + 1];
      }

    for (int i = 0; i < n; i++) f[i][0] = 0x3f3f3f3f;
    for (int i = 1; i < n; i++)
      for (int j = 1; j <= m; j++) {
        f[i][j] = 0x3f3f3f3f;
        for (int k = 0; k <= i; k++) {
          int t = cost[k][i];
          if (k) t += f[k - 1][j - 1];
          f[i][j] = min(f[i][j], t);
        }
      }

    return f[n - 1][m];
  }
};
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

时间复杂度$O(n^{2}m)$，空间$O(n^2)$。