#P17147. Push Box

Push Box

1011. Push Box

题目描述

数轴上有若干个带编号的箱子。第 ii 个箱子的初始位置是整数 aia_i,它需要在某个时刻到达过整数位置 bib_i,最后仍然回到并停留在 aia_i。

一次操作中,你可以选择一个箱子,将它向左或向右移动 11 个单位。任意时刻任意两个箱子都不能位于同一个整数位置。箱子可以被移动到负数位置。

对于每个 m=1,2,…,nm=1,2,\ldots,n,只考虑编号 11 到 mm 的箱子。你需要求出:使这 mm 个箱子都到达过各自的目标位置,并且最终全部回到初始位置的最少操作次数。

如果 ai=bia_i=b_i,则第 ii 个箱子在初始时刻就已经到达过目标位置。

输入格式

第一行包含一个整数 TT(1≤T≤1021\le T\le 10^2),表示测试数据的组数。

对于每组测试数据:

  • 第一行包含一个整数 nn(1≤n≤2×1051\le n\le 2\times 10^5)。
  • 第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(1≤ai≤1091\le a_i\le 10^9),表示箱子的初始位置。
  • 第三行包含 nn 个整数 b1,b2,…,bnb_1,b_2,\ldots,b_n(1≤bi≤1091\le b_i\le 10^9),表示箱子的目标位置。

保证同一组测试数据内 a1,a2,…,ana_1,a_2,\ldots,a_n 两两不同,且所有测试数据的 nn 之和不超过 10610^6。

输出格式

对于每组测试数据,输出一行 nn 个整数。第 mm 个整数表示只考虑编号 11 到 mm 的箱子时的最少操作次数。

答案可能为 00,并且可能超过 3232 位整数范围。

样例输入

2
2
2 3
3 1
3
2 1 4
3 1 2

样例输出

2 12
2 2 10

提示

第一组测试用例中,当 m=2m=2 时,一种最优方案如下:

  1. 将第 22 个箱子从 33 移动到 44;
  2. 将第 11 个箱子从 22 移动到 33;
  3. 将第 11 个箱子从 33 移动到 00;
  4. 将第 22 个箱子从 44 移动到 11;
  5. 将第 22 个箱子从 11 移动到 33;
  6. 将第 11 个箱子从 00 移动到 22。

总操作次数为 1+1+3+3+2+2=121+1+3+3+2+2=12。

来源:2026杭电多校-测试专用(山西实验) 原题链接:http://acm.hdu.edu.cn/contest/problem_show.php?cid=1234&pid=1011