P885 指针
指针
题目描述
有 台设备分布在一条数轴上,第 台设备的坐标为 。有 位维修工,初始时第 位维修工的位置为 。
这些设备共发生了 次故障,第 次故障的设备为 ,你需要指定一名维修工维修设备 ,他将从他当前所在的位置移动到位置 。维修工从位置 移动到位置 需要花费 的代价。
你需要合理调配维修工,在每次故障发生后及时完成维修,即必须依次完成 次维修。求所有维修的代价总和的最小值。
有 109 台设备分布在一条数轴上,第 i 台设备的坐标为 i。有 n 位维修工,初始时第 i 位维修工的位置为 ai。
这些设备共发生了 m 次故障,第 j 次故障的设备为 bj,你需要指定一名维修工维修设备 bj,他将从他当前所在的位置移动到位置 bj。维修工从位置 x 移动到位置 y 需要花费 ∣x−y∣ 的代价。
你需要合理调配维修工,在每次故障发生后及时完成维修,即必须依次完成 m 次维修。求所有维修的代价总和的最小值。