1478. 安排邮筒

发表于 分类于 阅读次数： Waline： 本文字数： 900 阅读时长 ≈ 3 分钟

考点

  • 划分DP
  • 前缀和
  • 中位数
  • 数学

题解

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
class Solution {
 public:
  static const int inf = 0x3f3f3f3f;
  int minDistance(vector<int>& houses, int k) {
    int n = houses.size();
    sort(houses.begin(), houses.end());
    // cost[l][r]打表
    int pre[105];
    pre[0] = 0;
    for (int i = 1; i <= n; ++i) pre[i] = houses[i - 1] + pre[i - 1];
    int cost[105][105];
    for (int i = 1; i <= n; ++i) {
      for (int j = i; j <= n; ++j) {
        int mid = (i + j) >> 1;
        int left = (mid - i) * houses[mid - 1] - (pre[mid - 1] - pre[i - 1]);
        int right = (pre[j] - pre[mid]) - ((j - mid) * houses[mid - 1]);
        cost[i][j] = left + right;
      }
    }
    // DP
    int f[105][105];
    memset(f, 0x3f, sizeof(f));
    // 预处理区间只有一个的时候，是前缀和
    for (int i = 1; i <= n; ++i) f[1][i] = cost[1][i];
    for (int j = 2; j <= k; ++j) {
      for (int r = j; r <= n; ++r) {
        for (int l = r; l >= j; --l) {
          if (f[j - 1][l - 1] != inf)
            f[j][r] = min(f[j][r], f[j - 1][l - 1] + cost[l][r]);
        }
      }
    }
    return f[k][n];
  }
};

思路

每个邮箱负责的房子下标集合是一个连续区间，这是本题最大的难点

假设按数轴分布如下，小写字母是房子，大写字母是邮箱

1
1 2 x 3 4 y 5 z 6 7

很显然，12到x的距离肯定小于到y的，那么[1, 2]肯定在一个区间内

至于3，可以变成[1, 2, 3]为x所处理，也可以组成[3, 4]为y所处理，因为3到z的距离肯定大于到y的

总而言之，

最优方案中，我们可以认为有 \(k\) 个区间： \[ [l_1, r_1], [l_2, r_2], \dots, [l_k, r_k] \] 满足 \[ 1 = l_1 \le r_1 < l_2 \le r_2 < \dots < l_k \le r_k = n \] 第 \(j\) 个区间的房子由第 \(j\) 个邮箱负责。

假设我们已经确定了一个区间 \([l, r]\)，对应的房子位置是： \[ h_l \le h_{l+1} \le \dots \le h_r \] 我们要在数轴上选一个点 \(p\)，使得代价 \[ F(p) = \sum_{i=l}^r |h_i - p| \] 最小。

这是一个经典问题：绝对值和在一维上的最优解是中位数，直接背下来就好，这是数学性质

而对于代价，我们需要预处理 \[ cost[l][r] = \sum_{i=l}^r |h_i - h_{mid}| \] 其中 \[ mid = \left\lfloor \frac{l + r}{2} \right\rfloor \] 最朴素的做法：三重循环，直接对每个 \((l, r)\) 再扫一遍求和，时间复杂度 \(O(n^3)\)，在本题 \(n \le 100\) 也能过，但可以更优。

用前缀和可以把计算 cost[l][r] 降到 \(O(1)\)，总复杂度 \(O(n^2)\)。

令 \[ pre[i] = \sum_{t=1}^i h_t,\quad pre[0] = 0 \] 对于任意 \(1 \le a \le b \le n\), \[ \sum_{t=a}^b h_t = pre[b] - pre[a-1] \] 然后代价拆成左右两部分

对区间 \([l, r]\)，中位数下标 \(mid\)，对应值 \(h_{mid}\)。把区间拆成左半和右半：

  • 左半：\([l, mid-1]\)，这里所有点都在中位数左边
  • 右半：\([mid+1, r]\)，这里所有点都在中位数右边 中位数自己距离是 0，可以忽略

于是： \[ cost[l][r] = \sum_{i=l}^r |h_i - h_{mid}| = \sum_{i=l}^{mid-1} (h_{mid} - h_i) + \sum_{i=mid+1}^r (h_i - h_{mid}) \] 分别处理两块。

对于左半部分 \[ \sum_{i=l}^{mid-1} (h_{mid} - h_i) = (mid - l) \cdot h_{mid} - \sum_{i=l}^{mid-1} h_i \] 注意左半的数量是 mid - l 个（不包括 mid 自己）。 其中 \[ \sum_{i=l}^{mid-1} h_i = pre[mid-1] - pre[l-1] \] 所以左边部分为： \[ left = (mid - l) \cdot h_{mid} - (pre[mid-1] - pre[l-1]) \] 对于右半部分 \[ \sum_{i=mid+1}^{r} (h_i - h_{mid}) = \sum_{i=mid+1}^{r} h_i - (r - mid)\cdot h_{mid} \] 其中 \[ \sum_{i=mid+1}^{r} h_i = pre[r] - pre[mid] \] 所以右边部分为： \[ right = (pre[r] - pre[mid]) - (r - mid)\cdot h_{mid} \] 最后合并，于是： \[ cost[l][r] = left + right = (mid - l) \cdot h_{mid} - (pre[mid-1] - pre[l-1]) + (pre[r] - pre[mid]) - (r - mid)\cdot h_{mid} \]