1185 山区建小学
大约 5 分钟
1185 山区建小学
【算法】 递推、DP(动态规划)
【C++】 二维数组、前缀和
【难度】 普及/提高−
一、题目简述
个村庄排在一条直线上,已知相邻村庄间距。从中选 个建小学(),使得所有村庄到最近小学的距离总和最小。求这个最小值。
示例:,距离数组
3 1 3 1 1 1 1 1 3,输出 。
二、解题思路
2.1 问题分析
两个子问题需要解决:
- 一段区间只建 1 所小学,建在哪?
- 如何把 个村庄划分给 所学校?
2.2 一段区间建 1 所小学——中位数原则
在一条直线上,要选一个点使各点到它的距离之和最小,这个点是中位数。
直观理解:小学往左偏一格,右边的人走更远;往右偏一格,左边的人走更远。站中间最公平。
例如村庄位置在 ,中位数在 处,距离和 。若放 处则为 ,更差。
设 为第 个村庄的坐标, 表示区间 内只建 1 所小学的最小距离和:
可以用前缀和在 内算出每个 ,预处理 。
2.3 全局 DP——划分区间
设 表示前 个村庄建 所小学的最小距离和。
考虑最后一所学校覆盖的区间 :
含义:前 个村庄用 所学校,第 所学校覆盖 到 。
边界:
- (1 所学校覆盖所有前 个村庄)
目标:
2.4 手动模拟
以 ,距离 [2, 3, 1] 为例。
第一步:预处理 (区间内 1 所小学)
| 区间 | 小学位置 | 距离和 | |
|---|---|---|---|
| 1 | |||
| 1 | |||
| 2 | |||
| 2 | |||
| 2 | |||
| 2 | |||
| 3 | |||
| 3 | |||
| 3 | |||
| 4 |
第二步:DP 填表
(边界):
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
(枚举 ,前 个村用 1 所, 到 用第 2 所):
最优方案:前 2 个村庄建第 1 所小学,村庄 3,4 建第 2 所小学,总距离 。
2.5 算法选择
,。预处理 为 ,DP 为 ,在 1s 内可行。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int M = 505;
const int INF = 0x3f3f3f3f;
int pos[M]; // 村庄坐标(前缀和)
int sum[M]; // pos 的前缀和,用于 O(1) 算 w
int w[M][M]; // w[i][j]: 区间 [i,j] 建 1 所小学的最小距离和
int dp[M][M]; // dp[i][j]: 前 i 个村庄建 j 所小学的最小距离和
// O(1) 计算 w[i][j]
int calcW(int i, int j) {
int mid = (i + j) / 2;
int left = (mid - i) * pos[mid] - (sum[mid - 1] - sum[i - 1]);
int right = (sum[j] - sum[mid]) - (j - mid) * pos[mid];
return left + right;
}
int main() {
int m, n;
cin >> m >> n;
// 读入距离,计算村庄坐标
pos[1] = 0; // 第一个村庄在位置 0
for (int i = 2; i <= m; i++) {
int d;
cin >> d;
pos[i] = pos[i - 1] + d;
}
// 坐标前缀和
for (int i = 1; i <= m; i++) {
sum[i] = sum[i - 1] + pos[i];
}
// 预处理 w[i][j]
for (int i = 1; i <= m; i++) {
for (int j = i; j <= m; j++) {
w[i][j] = calcW(i, j);
}
}
// DP
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= m; i++) {
dp[i][1] = w[1][i]; // 边界:1 所学校覆盖 1..i
for (int j = 2; j <= min(i, n); j++) {
for (int k = j - 1; k < i; k++) {
dp[i][j] = min(dp[i][j], dp[k][j - 1] + w[k + 1][i]);
}
}
}
cout << dp[m][n] << endl;
return 0;
}另一种写法(O(m²) 递推 w)
如果觉得前缀和公式不好理解,可以用简单的递推计算 :
// w[i][i] = 0
// w[i][j] = w[i][j-1] + pos[j] - pos[(i + j) / 2]
for (int i = 1; i <= m; i++) {
w[i][i] = 0;
for (int j = i + 1; j <= m; j++) {
w[i][j] = w[i][j - 1] + pos[j] - pos[(i + j) / 2];
}
}四、复杂度分析
- 时间复杂度: 预处理 + DP。,约 次运算,可接受。
- 空间复杂度:, 的二维数组约 1 MB。
五、思维拓展
| 知识点 | 说明 |
|---|---|
| 中位数最小化距离和 | 一维数轴上,中位数到各点距离和最小 |
| 区间 DP | 由更短的区间 转移 |
| 前缀和优化 | 公式化后 查询 |
类似题目:邮局选址(POJ 1160)、仓库选址问题。
六、易错点
- 村庄坐标:,后续 。注意 是 个数。
- 的中位数:(整数除法自动下取整),小学建在
pos[mid]。 - DP 枚举范围: 从 到 。前 所学校每个至少覆盖 1 个村庄,所以 至少为 。
- INF 初始化:
memset(dp, 0x3f, sizeof(dp))是常用技巧,0x3f3f3f3f≈ ,足够大且不溢出。
