本题的目标是重排序列 A,使得 ∑i=1n∣ai′−bi∣ 最小。
贪心配对策略
可以证明,将两个序列分别按数值从小到大排序后,让相同排名的元素两两配对,得到的绝对差之和最小。
因此,我们对 A 和 B 分别排序,排序后的 A 的第 k 小元素就应该对应排序后的 B 的第 k 小元素。
处理 B 不能移动的限制
有两个研究员小张和小王,他们分别记录了一组实验数据,得到了两个长度相同的整数序列 A 和 B。 但在记录过程中,小张不小心弄乱了序列 A 的顺序,而小王的序列 B 保持原样。 为了恢复实验的真实对应关系,他们决定将序列 A 重新排列,使得两个序列按位置匹配时的绝对差之和尽可能小。 形式化地,给定两个长度均为 n 的序列 A=[a1,a2,…,an] 和 B=[b1,b2,…,bn],你可以将序列 A 任意重排。 设重排后的序列为 A′,目标是最小化 ∑i=1n∣ai′−bi∣。 请你求出任意一个达到最小值的 A′。
约束条件:
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册