题目理解

字节国家剧院舞台区间 $[0, d]$，$0$ 和 $d$ 是后台。
每幕需要若干布景元素放在特定位置。
幕间需要搬运元素：

• 匹配 $A$ 中元素到 $B$ 中位置
• 多余元素搬回后台（$0$ 或 $d$）
• 缺少元素从后台搬来
• 一次只能搬一个，耗时 $|i-j|$
• 目标是最小化总时间

算法核心思想

这个解法的核心是将总代价表示为偏移量 $x$ 的函数，用差分数组快速计算所有可能偏移量下的代价，取最小值。

关键定义与符号

设：

• $n = |A|$, $m = |B|$
• $A$ 和 $B$ 已排序
• 定义偏移量 $x \in [-n, m]$，表示匹配方案为：
  • $A$ 中前 $n - \max(0, x)$ 个元素匹配 $B$ 中后 $m - \max(0, -x)$ 个元素
  • 实际上，$x$ 可以理解为 $A$ 中未匹配元素的数量（当 $x>0$）或 $B$ 中未匹配元素的数量（当 $x<0$）的一种映射

但在代码中，偏移量索引 $i$ 的范围是 $[0, n+m]$，对应 $x = i - n$。

代价组成分析

总代价 = 匹配代价 + 后台搬运代价

1. 后台搬运代价

• 如果 $x > 0$：有 $x$ 个 $A$ 中元素要搬回后台，$B$ 中元素全匹配
• 如果 $x < 0$：有 $-x$ 个 $B$ 中元素要从后台搬来，$A$ 中元素全匹配
• 后台在 $0$ 和 $d$，最优选择是每个元素去最近的后台

代码中简化处理：每个后台搬运固定代价 $d$
这意味着假设每次搬运都要横跨整个舞台（最坏情况），实际最优解会小于等于这个值，但由于我们取最小值，不影响最终结果。

初始化：

ans[0] += m * d;  // 初始假设所有B元素都要从后台搬来
for (int i = 1; i <= m; i++) 
    ans[i] += -d;  // 随着偏移变化，减少后台搬运代价
for (int i = m + 1; i <= n + m; i++) 
    ans[i] += d;   // 增加A到后台的代价

2. 匹配代价

对于每个 $A[i]$：

• 找到第一个 $B[j] \ge A[i]$
• 当偏移量 $x$ 较小时，$A[i]$ 匹配的 $B$ 位置在右边，距离 = $B_{i+x} - A[i]$
• 当偏移量 $x$ 较大时，$A[i]$ 匹配的 $B$ 位置在左边，距离 = $A[i] - B_{i+x}$
• 在转折点 $p = j - i - 1 + n$ 处符号变化

用差分数组记录这个变化：

add(ans, 0, p, A[i]);       // 前半段加A[i]
add(ans, p+1, m+n, -A[i]);  // 后半段减A[i]

对于每个 $B[i]$：

• 找到最后一个 $A[j] \le B[i]$
• 类似分析，在转折点 $p = i - j + 1 + n$ 处符号变化

add(ans, 0, p-1, -B[i]);    // 前半段减B[i]  
add(ans, p, m+n, B[i]);     // 后半段加B[i]

算法步骤

1. 初始化差分数组 ans，设置后台搬运代价
2. 处理A中元素：对每个 $A[i]$，找到匹配转折点，更新差分数组
3. 处理B中元素：对每个 $B[i]$，找到匹配转折点，更新差分数组
4. 前缀和还原实际代价数组
5. 遍历所有偏移量取最小值

时间复杂度

• 每次 solve 用时 $O(n \log m + m \log n)$（主要来自二分查找）
• 总元素数 $\le 5\times 10^5$，可接受

算法标签

• 差分数组（核心技巧）
• 二分查找
• 最优匹配
• 排序
• 一维运输问题

总结

该解法通过偏移量枚举和差分优化，将看似复杂的匹配问题转化为线性可解的问题，充分利用了一维距离的特性和最优匹配不交叉的性质，是组合优化与算法技巧的完美结合。