题目链接: 序列(sequence)

csdn食用更佳：序列(sequence)

思路分析

• 距离计算：
  定义两个序列 $a$ 和 $b$ 的距离为 $(\sum_{i=1}^{n} (a_i - b_i)^2)$。
  我们需要通过交换 $a$ 中的元素来最小化这个距离。

• 最小化距离：
  由于 $a$ 和 $b$ 中的元素都是唯一的，我们可以通过将 $a$ 中的元素重新排列，使得 $a_i$ 尽可能接近 $b_i$。
  具体来说，我们可以将 $a$ 和 $b$ 中的元素按相同的顺序排序，这样 $a_i$ 和 $b_i$ 的对应关系就是最优的。

• 计算最小交换次数：
  为了计算最少的交换次数，我们需要找到 $a$ 中的元素与 $b$ 中的元素之间的置换环。
  每个置换环的长度减去 $1$ 就是该环需要的交换次数。
  总的交换次数就是所有置换环的交换次数之和。

具体步骤

• 读取输入：

  • 读取 (n) 和 (T)。
  • 读取序列 $a$ 和 $b$。

• 计算最小距离：

  • 将 $a$ 和 $b$ 分别排序。
  • 计算排序后的 $a$ 和 $b$ 的距离。

• 计算最小交换次数如果 $T = 1$：

  • 构建一个映射，将 $a$ 中的每个元素映射到 $b$ 中的对应位置。
  • 使用深度优先搜索（DFS）或并查集来找到所有的置换环。
  • 计算每个置换环的长度，并求出总的交换次数。

代码实现

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

const int N = 6e5 + 5;
const long long MOD = 998244353;

int n, t;
pair<int, int> a[N], b[N];
int p[N];

int main()
{
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    scanf("%d %d", &n, &t);
    for (int i = 1; i <= n; ++i) 
	{
        scanf("%d", &a[i].first);
        a[i].second = i;
    }
    for (int i = 1; i <= n; ++i) 
	{
        scanf("%d", &b[i].first);
        b[i].second = i;
    }
    sort(a + 1, a + n + 1),sort(b + 1, b + n + 1);
    long long ans = 0;
    for (int i = 1; i <= n; ++i) 
	{
        p[a[i].second] = b[i].second;  // 将序列 A 中的元素对应到序列 B 中的位置
        ans = (ans + (long long)(a[i].first - b[i].first) * (a[i].first - b[i].first)) % MOD;
    }
    long long sum = 0;
    for (int i = 1; i <= n; ++i) 
	{
        while (p[i] != i)  // 如果当前位置的对应不是自己
		{
            swap(p[i], p[p[i]]); // 交换对应关系，使其正确
            sum++;
        }
    }
    printf("%lld ", ans);
    if (t == 1) 
	{
        printf("%lld\n", sum);
    }
    return 0;
}