Post Office Problem
2024-08-21 17:49:50
Description
There are n
houses on a line. Given an array A
and A[i]
represents the position of i-th
house. Now you need to pick k
position to build k
post offices.
What is the minimum sum distance from these n
houses to the nearest post office?
All positions are integers.
Example
Example 1:
Input: A = [1, 2, 3, 4, 5], k = 2
Output: 3
Explanation: Build post offices on position 2 and 4.
Example 2:
Input: A = [1, 2], k = 1
Output: 1
Explanation: Build post office on position 1 or 2.
Challenge
O(n^2) time
思路:
线性动态规划 (而不是区间动态规划)
可以按照每个房子最近的邮局, 把 n
个房子分成 k
段, 而我们要决定的就是这 k
段分别是多长. 为了处理方便我们先对房子的位置排序.
设定 f[i][j] 表示前 j 栋房子建立 i 个邮局时的最优解. 对于这个状态我们需要决策的就是 j 之前有多少栋房子共用第 i 个邮局, 故有:
f[i][j] = min{f[i - 1][j - x] + sumdis[j - x][j - 1]}
其中 sumdis[l][r] 表示下标范围为 [l, r] 的房子之间建立一个邮局, 这些房子与该邮局的最短距离
(注意f[i][j]中的j表示的第j栋房子从1计数, sumdis从0计数)
sumdis数组可以实现预处理出来, 具体算法与中位数的性质有关. 即对于 sumdis[l][r], 直接选择这 r - l + 1 栋房子中, 中间的那一栋建立邮局(如果是偶数栋, 中间的两栋任选一栋), 这时这些房子与邮局的距离之和是最短的.
至于dp的边界: f[i][0] = 0, f[0][j] = INF, 以及 i >= j 时 f[i][j] = 0
另外, 这样的状态定义可以用滚动数组优化空间.
public class Solution {
/**
* @param A an integer array
* @param k an integer
* @return an integer
*/
int[][] init(int[] A) {
int n = A.length;
int[][] dis = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; ++j) {
int mid = (i + j) / 2;
for (int k = i; k <= j; ++k)
dis[i][j] += Math.abs(A[k - 1] - A[mid - 1]);
}
}
return dis;
} public int postOffice(int[] A, int k) {
// Write your code here
int n = A.length;
Arrays.sort(A); int[][] dis = init(A);
int[][] dp = new int[n + 1][k + 1];
if (n == 0 || k >= A.length)
return 0;
int ans = Integer.MAX_VALUE;
for (int i = 0; i <= n; ++i) {
dp[i][1] = dis[1][i]; } for (int nk = 2; nk <= k; nk++) {
for (int i = nk; i <= n; i++) {
dp[i][nk] = Integer.MAX_VALUE;
for (int j = 0; j < i; j++) {
if (dp[i][nk] == Integer.MAX_VALUE || dp[i][nk] > dp[j][nk - 1] + dis[j + 1][i])
dp[i][nk] = dp[j][nk - 1] + dis[j + 1][i];
}
}
}
return dp[n][k];
}
}
最新文章
- BZOJ 2002: [Hnoi2010]Bounce 弹飞绵羊
- HTML页面和JSP页面禁止缓存
- 多个SVG图形集成到一个SVG图形上
- ServiceStack 概念参考文摘
- maven之window安装
- Linux 中open系统调用实现原理【转】
- ios 企业发布
- perl 访问类方法的几种方式
- Android源代码学习之六——ActivityManager框架解析
- ASP.NET MVC+EF框架+EasyUI实现权限管理系列(8)-DbSession线程内唯一
- Sass编译Css
- frame间跳转及相关问题
- Jquery AutoComplete实现搜索自动完成
- (转ORCLE导入导出命令)
- 基于Spring注解搭建SpringMVC项目
- Netty入门(一)之webSocket聊天室
- [js]js中类的继承
- angular6新建项目
- nodejs 在线学习课堂
- 浅析Java虚拟机结构与机制[转]