每个人到达目的地的最短时间
Shortest time for everyone to get to the destination
我要设计一个算法来解决一个问题：
我们有两组人（A组和B组，A组的人数总是小于或等于B组的人数），都站在一个一维的直线上，每个人都有一个对应的编号指示其位置。当计时器开始时，A组的每个人必须找到B组的伙伴，但是B组的人根本不能移动，B组的每个人最多只能有1个伙伴。
假设A组的人第1步unit/sec，如何求出A组所有人找到搭档的最短时间？
例如，如果 A 组中有三个人，位置为 {5,7,8}，B 组中有四个人，位置为 {2,3,4,9}，则最优解为 3秒 因为 max(5-3,7-4,9-8)=3
我只能用暴力破解，请问有没有更好的方法解决这个问题？
这道题是edit distance problem的特例，可以用类似的动态规划法来求解。对于这种特殊情况，可能存在更快的解决方案。
令A = [a_0, a_1...,a_(m-1)]为我们m移动人员的（排序）位置，B = [b_0, b_1...,b_(n-1)]为n（排序）目的地，m <= n.对于编辑距离类比，允许的操作是：
- 将数字插入
A（免费），或
- 用成本
|a-a'| 替换 A 中的元素 a -> a'。
我们可以在 O(n*m) 时间内解决这个问题（如有必要，加上 A 和 B 的排序时间）。
我们可以通过成本函数 C(i, j) 定义动态规划，这是仅使用前 j 个地点移动前 i 人 a_0, ... a_(i-1) 的最低成本b_0, ... b_(j-1)。你想要C(m,n)。定义C如下：
我要设计一个算法来解决一个问题： 我们有两组人（A组和B组，A组的人数总是小于或等于B组的人数），都站在一个一维的直线上，每个人都有一个对应的编号指示其位置。当计时器开始时，A组的每个人必须找到B组的伙伴，但是B组的人根本不能移动，B组的每个人最多只能有1个伙伴。
假设A组的人第1步unit/sec，如何求出A组所有人找到搭档的最短时间？
例如，如果 A 组中有三个人，位置为 {5,7,8}，B 组中有四个人，位置为 {2,3,4,9}，则最优解为 3秒 因为 max(5-3,7-4,9-8)=3
我只能用暴力破解，请问有没有更好的方法解决这个问题？
这道题是edit distance problem的特例，可以用类似的动态规划法来求解。对于这种特殊情况，可能存在更快的解决方案。
令A = [a_0, a_1...,a_(m-1)]为我们m移动人员的（排序）位置，B = [b_0, b_1...,b_(n-1)]为n（排序）目的地，m <= n.对于编辑距离类比，允许的操作是：
- 将数字插入
A（免费），或 - 用成本
|a-a'|替换A中的元素a -> a'。
我们可以在 O(n*m) 时间内解决这个问题（如有必要，加上 A 和 B 的排序时间）。
我们可以通过成本函数 C(i, j) 定义动态规划，这是仅使用前 j 个地点移动前 i 人 a_0, ... a_(i-1) 的最低成本b_0, ... b_(j-1)。你想要C(m,n)。定义C如下：