正经题解｜排列

提示

不考虑整齐度，如何交换元素让所有元素归位，能够使得交换的次数最少？

题目解析

如果不考虑整齐度，交换元素让所有元素归位，我们可以考虑让每个元素直接回到他的位置试试看。以样例 [2, 1, 4, 5, 3] 为例，为了方便我们令 t 为待交换元素（搁置元素）。
令 t = 2，放回到它的位置 i = 2，此时 a[2] = 1，把 1 设为搁置元素。
此时 t = 1，数组为 [2, 2, 4, 5, 3]；
然后我们再将搁置元素 t = 1 放到 i = 1，此时数组为 [1, 2, 4, 5, 3]，下标为 1, 2 的元素已归位。
同理我们可以使用以上方法使剩余元素归位。

不难发现，每一轮交换总是从一个位置 $i$ 开始，然后回到 $i$ 结束，形成一个环。

每个元素只会与其所在环内的元素交换，且让一个有 $m$ 个元素的环的所有元素归位，只需要 $m-1$ 次交换。

接着我们考虑交换次数受限制的情况。比如对于一个大小为 $m$ 的环，我们可以交换元素的次数只有 $k(1 \le k < m - 1)$ 次，那么对于这个大小为 $m$ 的环，我们最多只能使 $k$ 个元素归位。

由于题目中我们让每个元素归位获得的 整齐度 是不一样的，所以对于一个环我们如果只能归位有限个元素，显然应该选择优先归位权重（ 整齐度 ）更大的元素。所以归位一个环内的元素时，可以将环内元素按照权重从大到小排序，优先归位权重更大的元素。

接下来问题便可以转化成：数组中不在自己位置上的元素形成 $n$ 个环，对于每个环可以选择归位若干个元素 $b_i (1 \le i \le n)$，限制为 $b_1 + b_2 + \cdots + b_n \le k$ 。
那么由于每个元素归位的权重不同，对于每个大小为 $m$ 的环，实际上我们只需要关注在环中选择归位元素的数量即可，不需要枚举环中具体归位哪些元素。即选择 环中归位的元素数量 即可。

那么这里问题便转化为了一个 分组背包 问题：
有 $n$ 个环，最多操作 $k$ 次。
每个环可以选择归位元素的数量。
环 $i$ 选择归位 $j$ 个元素的操作次数为

$$v_{ij} = \begin{cases} j - 1, &\text{if j = m}\\ j, &\text{if j < m} \end{cases}$$

获得的 整齐度 为 $sum_{ij}$ 即环 $i$ 中权重最大的 $j$ 个元素的 整齐度 之和。
求解每个环选择归位多少个元素，操作次数总和不超过 $k$，且获得的 整齐度 最大。

对于本题的答案就是分组背包处理完后的答案加上已经在位置上的元素的 整齐度 之和。

AC代码

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<int> a(n), v(n);
    for (auto &x : a) cin >> x, --x;
    for (auto &x : v) cin >> x;
    vector<i64> dp(k+1);
    i64 res = 0;
    vector<int> st(n);
    for (int lo = 0; lo < n; ++lo) {
        // 位置正确直接累加整齐度
        if (a[lo] == lo) {
            res += v[lo];
            continue;
        }
        // 已处理过的环内元素跳过
        if (st[lo] == 1) continue;
        // 处理环内元素
        vector<i64> sum;
        int hi = lo;
        do {
            sum.push_back(v[hi]);
            st[hi] = 1;
            hi = a[hi];
        } while (hi != lo);
        // 从大到小排序并求前缀和
        sort(sum.rbegin(), sum.rend());
        partial_sum(begin(sum), end(sum), begin(sum));
        // 分组背包
        int m = sum.size();
        for (int i = k; i > 0; --i) {
            for (int j = min(m - 1, i); j > 0; --j)
                if (j == m - 1)
                    dp[i] = max(dp[i], dp[i-j] + sum[j]);
                else
                    dp[i] = max(dp[i], dp[i-j] + sum[j-1]);
        }
    }
    cout << res + dp[k] << '\n';
    return 0;
}

复杂度分析

找出整个数组的所有环的时间复杂度为 $O(n)$。
对于分组背包的问题，时间复杂度为 所有物品数量的总和 $\times$ 背包容量，本题 所有物品数量的总和 显然不超过 $n$，总的时间复杂度为 $O(n \cdot k)$ 。