Bzeroth大陆最终还是覆灭了,所以你需要为地灾军团服务了。
地灾军团军师黑袍不擅长写题面,所以你只需要看简化版的题意即可。
给定 $3$ 个长度均为 $N$ 的正整数序列 $A$、$B$、$C$,要求从三个序列中分别取出 $1$ 个数 $A_i$、$B_j$、$C_k$,使得 $|A_i - B_j|+|A_i - C_k|+|B_j - C_k|$ 最小。
输入格式
第一行一个正整数 $N$。
第二行 $N$ 个正整数,第 $i$ 个数为 $A_i$。
第三行 $N$ 个正整数,第 $i$ 个数为 $B_i$。
第四行 $N$ 个正整数,第 $i$ 个数为 $C_i$。
输出格式
输出 $|A_i - B_j|+|A_i - C_k|+|B_j - C_k|$ 的最小值。
样例
input
3 170 180 190 195 185 175 180 160 200
output
10
explanation
选择 $A_2$、$B_2$、$C_1$ 或 $A_2$、$B_3$、$C_1$ 。
限制与约定
测试数据编号 | $N$ |
---|---|
1 | $=10$ |
2 | $=20$ |
3 | $=50$ |
4 | $=100$ |
5 | $=200$ |
6 | $=501$ |
7 | $=2501$ |
8 | $=5010$ |
9 | $=52501$ |
10 | $=152501$ |
对于 $100\texttt{%}$ 的数据:$1 \leq A_i、B_i、C_i \leq 10^9$。
时间限制:$1\texttt{s}$
空间限制:$128\texttt{MB}$