广西最新疫情通报_下载京东商城_魔贝课凡seo课程好吗_sem运营有出路吗

Exercise （ 2022 ICPC Southeastern Europe Regional Contest ）

In a classroom, there are $2n$ students. The $i$-th student has skill $c_i$. A teacher is holding an exercise that requires working in pairs. Initially, students $2i-1$ and $2i$ are paired, for each $i$ from $1$ to $n$.

Now, the teacher wants to form new pairs $(a_1,b_1),(a_2,b_2),\dots ,(a_n,b_n)$ with the following conditions:

• Each student is in exactly one pair. That is, each number from $1$ to $2n$ appears among numbers $a_1,a_2,\dots ,a_n,b_1,b_2,\dots ,b_n$ exactly once.

• No two students that were in a pair before will be in a pair again. That is, there are no $1\le i,j\le n$ such that $a_i=2j-1,b_i=2j$, or $a_i=2j,b_i=2j-1$.

The teacher wants to minimize the sum of differences in skills over the $n$ pairs, as this would be more productive. In other words, $|c_{a_1}-c_{b_1}|+|c_{a_2}-c_{b_2}|+\dots +|c_{a_n}-c_{b_n}|$ should be as small as possible.

What is the smallest value of $|c_{a_1}-c_{b_1}|+|c_{a_2}-c_{b_2}|+\dots +|c_{a_n}-c_{b_n}|$ the teacher can achieve?

Input

The first line of the input contains a single integer $n$ $(2\le n\le 100000)$.

The second line of the input contains $2n$ integers $c_1,c_2,\dots ,c_{2n}$ $(0\le c_i\le 10^9)$ — the skills of the students.

Output

Output a single integer — the smallest possible value of $|c_{a_1}-c_{b_1}|+|c_{a_2}-c_{b_2}|+\dots +|c_{a_n}-c_{b_n}|$ that the teacher can achieve.

Examples

Input

2
1 2 3 4

Output

4

Input

3
1 9 3 4 2 6

Output

7

Note

In the first example, the teacher can pair up the first student with the third and the second student with the fourth, getting $|3-1|+|4-2|=4$.

In the second example, the teacher can pair up the first student with the third, the second with the sixth, and the fourth with the fifth, getting $|1-3|+|9-6|+|4-2|=7$.

题面描述

在一个教室中有 $2n$ 个学生，每个学生有一个技能值 $c_i$。老师要进行一个练习，要求学生两两配对。初始时，学生 $2i-1$ 和 $2i$ 是配对的，其中 $i$ 从 $1$ 到 $n$。

现在，老师想要重新配对，满足以下条件：

1. 每个学生必须且只能出现在一个配对中。
2. 不允许两个之前已经配对过的学生再次配对。

老师希望最小化所有配对中技能值差异的总和，即 $|c_{a_1}-c_{b_1}|+|c_{a_2}-c_{b_2}|+\dots +|c_{a_n}-c_{b_n}|$ 尽可能小。

输入

• 第一行包含一个整数 $n$ $(2\le n\le 100,000)$。
• 第二行包含 $2n$ 个整数 $c_1,c_2,\dots ,c_{2n}$ $(0\le c_i\le 10^9)$，表示每个学生的技能值。

输出

输出一个整数，表示老师可以达到的最小技能值差异总和。

示例

输入 1:

2
1 2 3 4

输出 1:

4

输入 2:

3
1 9 3 4 2 6

输出 2:

7

题解

这个问题可以通过动态规划来解决。我们需要找到一种配对方式，使得所有配对中技能值差异的总和最小，并且不违反配对的条件。

解题思路

1. 排序：首先将所有学生按照技能值从小到大排序。这样我们可以更容易地找到技能值相近的学生进行配对。
2. 动态规划：使用动态规划来计算最小差异总和。定义 dp[i] 表示前 i 个学生的最小差异总和。
3. 状态转移：
   • 对于每个学生 i，我们可以尝试将其与 i-1 配对，或者跳过 i-1 并与 i-2 配对，依此类推。
   • 我们需要确保不违反配对的条件，即不能将之前已经配对过的学生再次配对。
4. 边界条件：dp[0] = 0，表示没有学生时的差异总和为 0。

代码分析

#include <map>
#include <set>
#include <fstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <iomanip>
#define endl '\n'
#define int long long
#define Max(a, b) (((a) > (b)) ? (a) : (b))
#define Min(a, b) (((a) < (b)) ? (a) : (b))
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;const int inf = 1e18 + 7;
const int N = 2e5 + 10;map<int, int> mp;
vector<int> dp(N, inf);
struct Node
{int value;int id;
} v[N + 1], vv[N + 1];int cmp(Node x, Node y)
{if (x.value == y.value){return x.id < y.id;}return x.value < y.value;
}void solved()
{dp[0] = 0;int n;cin >> n;for (int i = 1; i <= 2 * n; ++i){cin >> v[i].value;v[i].id = i;vv[i].value = v[i].value;vv[i].id = i;}for (int i = 2; i <= 2 * n; i += 2){mp[v[i].id] = v[i - 1].id;mp[v[i - 1].id] = v[i].id;}sort(vv + 1, vv + 2 * n + 1, cmp);for (int i = 1; i <= 2 * n; i += 2){if (mp[vv[i].id] != vv[i + 1].id){dp[i + 1] = min(dp[i + 1], dp[i - 1] + abs(vv[i + 1].value - vv[i].value));if (i >= 3){if (mp[vv[i + 1].id] != vv[i - 1].id && mp[vv[i].id] != vv[i - 2].id){dp[i + 1] = min(dp[i + 1], dp[i - 3] + abs(vv[i + 1].value - vv[i - 1].value) + abs(vv[i].value - vv[i - 2].value));}}if (i >= 5){if (mp[vv[i + 1].id] != vv[i - 1].id && mp[vv[i].id] != vv[i - 3].id && mp[vv[i - 2].id] != vv[i - 4].id){dp[i + 1] = min(dp[i + 1], dp[i - 5] + abs(vv[i + 1].value - vv[i - 1].value) + abs(vv[i].value - vv[i - 3].value) + abs(vv[i - 2].value - vv[i - 4].value));}}}else{if (i >= 3){dp[i + 1] = min(dp[i + 1], dp[i - 3] + abs(vv[i + 1].value - vv[i - 1].value) + abs(vv[i].value - vv[i - 2].value));}if (i >= 5){if (mp[vv[i + 1].id] != vv[i - 1].id && mp[vv[i].id] != vv[i - 3].id && mp[vv[i - 2].id] != vv[i - 4].id){dp[i + 1] = min(dp[i + 1], dp[i - 5] + abs(vv[i + 1].value - vv[i - 1].value) + abs(vv[i].value - vv[i - 3].value) + abs(vv[i - 2].value - vv[i - 4].value));}}}}cout << dp[2 * n];
}signed main()
{BoBoowen;int T = 1;// cin >> T;while (T--){solved();}
}

代码分析

1. 输入处理：首先读取学生数量 n 和每个学生的技能值，并记录每个学生的初始配对关系。
2. 排序：将所有学生按照技能值排序，方便后续的配对操作。
3. 动态规划：通过遍历排序后的学生列表，计算最小差异总和。对于每个学生，尝试与前面的学生进行配对，并更新 dp 数组。
4. 输出结果：最终输出 dp[2 * n]，即所有学生的最小差异总和。

总结

这个问题通过动态规划和排序的结合，有效地解决了最小化技能值差异总和的问题。代码中通过 dp 数组记录每一步的最小差异总和，并通过条件判断确保不违反配对的条件。