CF1661A.Array Balancing

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You are given two arrays of length $n$ : $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ .

You can perform the following operation any number of times:

Choose integer index $i$ ( $1 \le i \le n$ );
Swap $a_i$ and $b_i$ .

What is the minimum possible sum $|a_1 - a_2| + |a_2 - a_3| + \dots + |a_{n-1} - a_n|$ $+$ $|b_1 - b_2| + |b_2 - b_3| + \dots + |b_{n-1} - b_n|$ (in other words, $\sum\limits_{i=1}^{n - 1}{\left(|a_i - a_{i+1}| + |b_i - b_{i+1}|\right)}$ ) you can achieve after performing several (possibly, zero) operations?

输入格式

The first line contains a single integer $t$ ( $1 \le t \le 4000$ ) — the number of test cases. Then, $t$ test cases follow.

The first line of each test case contains the single integer $n$ ( $2 \le n \le 25$ ) — the length of arrays $a$ and $b$ .

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^9$ ) — the array $a$ .

The third line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ( $1 \le b_i \le 10^9$ ) — the array $b$ .

输出格式

For each test case, print one integer — the minimum possible sum $\sum\limits_{i=1}^{n-1}{\left(|a_i - a_{i+1}| + |b_i - b_{i+1}|\right)}$ .

输入输出样例

输入#1

3
4
3 3 10 10
10 10 3 3
5
1 2 3 4 5
6 7 8 9 10
6
72 101 108 108 111 44
10 87 111 114 108 100

输出#1

0
8
218

说明/提示

In the first test case, we can, for example, swap $a_3$ with $b_3$ and $a_4$ with $b_4$ . We'll get arrays $a = [3, 3, 3, 3]$ and $b = [10, 10, 10, 10]$ with sum $3 \cdot |3 - 3| + 3 \cdot |10 - 10| = 0$ .

In the second test case, arrays already have minimum sum (described above) equal to $|1 - 2| + \dots + |4 - 5| + |6 - 7| + \dots + |9 - 10|$ $= 4 + 4 = 8$ .

In the third test case, we can, for example, swap $a_5$ and $b_5$ .

首页