TwoMatchings - 题解

标签与难度

标签: 动态规划, 贪心, 图论, 组合优化, 排序 难度: 2000

题目大意喵~

主人你好呀，喵~ 这道题是关于排列和匹配的呢！

首先，题目定义了一种特殊的排列叫做“匹配”（matching）。一个长度为 $n$ 的排列 $p$ 是一个匹配，需要满足两个条件：

1. 对于所有的 $i$，都有 $p_i \ne i$（也就是说，没有元素在自己的位置上）。
2. 对于所有的 $i$，都有 $p_{p_i} = i$（如果 $i$ 指向 $j$，那么 $j$ 也必须指向 $i$）。

这两个条件合起来的意思是，一个匹配把 $1$ 到 $n$ 的所有数字两两配成对。比如说，如果 $p_1=3$，那么一定有 $p_3=1$，这样 $(1, 3)$ 就是一对。因为 $n$ 是偶数，所有 $n$ 个数字都可以被完美地分成 $n/2$ 个对。

接着，题目定义了匹配的“代价”（cost）。给定一个数组 $a$，一个匹配 $p$ 的代价是所有配对 $(i, p_i)$ 的 $a$ 值差的绝对值之和的一半，也就是 $\left(\sum_{i=1}^{n} |a_i - a_{p_i}|\right) / 2$。因为每一对 $(i, j)$ 在求和中被计算了两次（一次是 $|a_i - a_j|$，一次是 $|a_j - a_i|$），所以这个代价其实就是所有配对 $(i, j)$ 的 $|a_i - a_j|$ 之和，喵~

然后，又定义了两个匹配 $p$ 和 $q$ 是“可组合的”（combinable），当且仅当对于所有的 $i$，都有 $p_i \ne q_i$。也就是说，对于任何一个数字 $i$，它在匹配 $p$ 中的伙伴和在匹配 $q$ 中的伙伴是不同的。

最终任务：找到两个可组合的匹配 $p$ 和 $q$，使得它们的代价之和 Cost(p) + Cost(q) 最小，并输出这个最小的总代价。题目保证 $n \ge 4$ 且为偶数。

解题思路分析

这道题看起来有点复杂，又是匹配又是组合的，但别担心，跟着本喵的思路一步步来，很快就能理清啦，喵~

第一步：排序与代价简化

看到要最小化差值的和，我们的第一反应通常是... 排序！这是一个非常经典的贪心思路。为了让差值之和最小，我们应该让数值上相近的元素配对。所以，我们先把数组 $a$ 从小到大排个序。这样一来，对于任意一对 $(i, j)$ 且 $i < j$，它们的差值就是 $a_j - a_i$ 啦。

排序后，我们处理的就不再是原始的下标，而是排序后数组的下标 $1, 2, \dots, n$。

第二步：图论视角看问题

让我们换个角度看问题。把 $1, 2, \dots, n$ 这 $n$ 个下标看作图上的 $n$ 个节点。 一个匹配 $p$ 就是图上的一组边，这组边构成了 $n/2$ 个互不相交的对，我们称之为“完美匹配”。 同理，匹配 $q$ 也是一个完美匹配。

“可组合”的条件 $p_i \ne q_i$ 意味着 $p$ 和 $q$ 的边集是完全不相交的。 把这两个匹配的边画在同一个图上，我们会得到一个什么样的结构呢？ 图中的每个节点的度数都正好是 2（一个来自 $p$ 的边，一个来自 $q$ 的边）。一个所有节点度数都为 2 的图，必然是由一个或多个互不相交的环组成的！

因为 $p$ 和 $q$ 的边不重复，所以这些环的长度至少是 3。又因为环上的边可以交替地用 $p$ 和 $q$ 的边来“染色”，一个环要能同时容纳两个完美匹配，它的长度必须是偶数。所以，这些环的长度至少是 4。

所以，问题被我们转化成了：将 $n$ 个节点划分成若干个不相交的偶数长度的环（长度 $\ge 4$），使得总代价最小。

第三步：环的代价是多少？

现在我们来计算一个环的总代价。假设我们有一个长度为 $2k$ 的环，它包含了节点 $\{v_1, v_2, \dots, v_{2k}\}$。我们可以这样构造 $p$ 和 $q$：

• $p = \{(v_1, v_2), (v_3, v_4), \dots, (v_{2k-1}, v_{2k})\}$
• $q = \{(v_2, v_3), (v_4, v_5), \dots, (v_{2k}, v_1)\}$

（当然还有别的构造方式，但它们的代价是一样的）。 这个环的总代价是 Cost(p) + Cost(q)，等于环上所有边的 $|a_v - a_u|$ 之和。 TotalCost_cycle = $\sum_{i=1}^{2k-1} |a_{v_i} - a_{v_{i+1}}| + |a_{v_{2k}} - a_{v_1}|$。

为了让这个环的代价最小，我们应该选择哪些节点呢？直觉告诉我们，应该选择排序后连续的 $2k$ 个节点，比如说 $\{i, i+1, \dots, i+2k-1\}$。 在这些连续的节点上，如何连成一个环才能使边权和（即代价）最小呢？ 最小的代价来自于将它们按顺序连接：$i \to i+1 \to \dots \to i+2k-1 \to i$。

让我们来计算一下这个由连续节点构成的“顺序环”的代价。

• $p$ 的配对是 $\{(i, i+1), (i+2, i+3), \dots\}$。
• $q$ 的配对是 $\{(i+1, i+2), (i+3, i+4), \dots, (i+2k-1, i)\}$。 总代价为：

$$\text{Cost}_p = \sum_{j=0}^{k-1} (a_{i+2j+1} - a_{i+2j})$$

$$\text{Cost}_q = \left(\sum_{j=0}^{k-2} (a_{i+2j+2} - a_{i+2j+1})\right) + (a_{i+2k-1} - a_i)$$

把它们加起来，你会发现中间的项都神奇地抵消掉了，喵~ TotalCost = $(a_{i+1}-a_i) + (a_{i+3}-a_{i+2}) + \dots + (a_{i+2k-1}-a_{i+2k-2})$$+ (a_{i+2}-a_{i+1}) + (a_{i+4}-a_{i+3}) + \dots + (a_{i+2k-1} - a_i)$$= (-a_i) + (a_{i+2k-1}) + (a_{i+2k-1} - a_i) = 2 \times (a_{i+2k-1} - a_i)$

哇！一个由连续 $2k$ 个节点构成的最小代价环，其总代价就是 2 * (最大值 - 最小值)！

第四步：动态规划！

现在问题变成了：将排序后的数组 $a$ 切分成若干个连续的段，每段的长度是偶数且 $\ge 4$。对于每段（比如从下标 $j$ 到 $i$），其贡献的代价是 $2 \times (a_i - a_j)$。我们的目标是让所有段的代价之和最小。

这不就是一个完美的动态规划问题嘛！

状态定义: dp[i] 表示将前 $i$ 个元素（a[1] 到 a[i]）划分成符合要求的环的最小总代价。这里 i 必须是偶数。

核心洞察: 一个长度为 $2k$（$k \ge 4$）的环，代价是 $2(a_{i+2k-1} - a_i)$。 如果我们将它拆分成两个环，比如一个长度为 4，一个长度为 $2k-4$。 拆分后的代价是 $2(a_{i+3} - a_i) + 2(a_{i+2k-1} - a_{i+4})$。 比较一下： $2(a_{i+2k-1} - a_i)$ vs $2(a_{i+3} - a_i + a_{i+2k-1} - a_{i+4})$$0$ vs $a_{i+3} - a_{i+4}$ 因为数组 $a$ 是排好序的，所以 $a_{i+3} \le a_{i+4}$，因此 $a_{i+3} - a_{i+4} \le 0$。 这意味着拆分环总是更优或者一样好！

这个发现太重要了！它告诉我们，任何最优的划分方案，都可以只由长度为 4 和 6 的环组成。因为任何更长的偶数长度环（如 8, 10, 12...）都可以被拆成 4 和 6 的组合，并且代价更小。

• 长度 8 的环可以拆成两个长度 4 的环。
• 长度 10 的环可以拆成一个 4 和一个 6。
• ...以此类推。

所以，我们的 DP 转移方程就变得非常简单了！

DP 转移方程: 要计算 dp[i]，我们可以考虑最后一个环（段）的长度：

1. 如果最后一个环长度为 4，它由元素 a[i-3] 到 a[i] 组成。这要求我们已经算好了 dp[i-4]。总代价是 dp[i-4] + 2 * (a[i] - a[i-3])。
2. 如果最后一个环长度为 6，它由元素 a[i-5] 到 a[i] 组成。这要求我们已经算好了 dp[i-6]。总代价是 dp[i-6] + 2 * (a[i] - a[i-5])。

所以，dp[i] 就是这两者中的较小值：

$$dp[i] = \min(dp[i-4] + 2 \times (a_i - a_{i-3}), \quad dp[i-6] + 2 \times (a_i - a_{i-5}))$$

DP 初始条件:

• dp[0] = 0 (前 0 个元素代价为 0)
• dp[i] = infinity 对于奇数 i 或 i=2 (无法划分)
• dp[4] = 2 * (a[4] - a[1]) (前 4 个元素只能组成一个 4-环)
• dp[6] = 2 * (a[6] - a[1]) (前 6 个元素只能组成一个 6-环)

最终的答案就是 dp[n] 啦！

代码实现

下面是本喵根据上面的思路，精心为你准备的代码哦~

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

// 使用 long long 来防止代价溢出，喵~
using ll = long long;

void solve() {
    int n;
    std::cin >> n;
    std::vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 第一步，对数组 a 进行排序
    std::sort(a.begin(), a.end());

    // dp[i] 表示处理前 i 个元素（a[0]...a[i-1]）的最小代价
    std::vector<ll> dp(n + 1, LLONG_MAX);

    // 初始条件
    dp[0] = 0;

    // 开始递推，i 代表处理的元素个数
    for (int i = 2; i <= n; i += 2) {
        // 方案一：最后一个环是 4-环
        // 这个环由 a[i-4], a[i-3], a[i-2], a[i-1] 组成
        if (i >= 4 && dp[i - 4] != LLONG_MAX) {
            ll cost_4_cycle = 2 * (a[i - 1] - a[i - 4]);
            dp[i] = std::min(dp[i], dp[i - 4] + cost_4_cycle);
        }

        // 方案二：最后一个环是 6-环
        // 这个环由 a[i-6], ..., a[i-1] 组成
        if (i >= 6 && dp[i - 6] != LLONG_MAX) {
            ll cost_6_cycle = 2 * (a[i - 1] - a[i - 6]);
            dp[i] = std::min(dp[i], dp[i - 6] + cost_6_cycle);
        }
    }

    std::cout << dp[n] << std::endl;
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O(T \cdot N \log N)$ 每个测试用例中，最耗时的部分是排序，需要 $O(N \log N)$ 的时间。之后的动态规划部分是一个简单的循环，只需要 $O(N)$ 的时间。所以总时间复杂度由排序决定，为 $O(N \log N)$。

• 空间复杂度: $O(N)$ 我们需要一个大小为 $N$ 的数组 a 来存储输入，以及一个大小为 $N+1$ 的 dp 数组来存储动态规划的状态。所以空间复杂度是 $O(N)$。

知识点总结

这道题真是一次有趣的冒险，我们用到了好几种强大的工具呢！

1. 贪心思想: 遇到最小化差值和的问题，首先想到排序，这能极大地简化问题。
2. 问题转化: 把抽象的排列和组合问题，转化为更直观的图论模型（节点划分成偶数环），是解题的关键一步。
3. 代价分析: 通过分析环的代价，我们得出了一个简洁的代价公式 2 * (max - min)，并且发现了拆分大环更优的重要性质。
4. 动态规划 (DP): 最终，我们将问题归结为一个一维 DP。核心洞察（只用 4-环和 6-环）让复杂的 DP 转移变得异常简单。

希望这篇题解能帮助到你，如果还有不明白的地方，随时可以再来问本喵哦！祝你刷题愉快，喵~