1224-交换瓶子

#personal/blog

题目描述

关系

内容

问题分析

最初思路

如果一个数，不在其对应的坑位，那么是一定要进行交换的。找谁交换呢？假设数 a 占据了错误的坑位 i，数 b 占据了错误的坑位 j，如果 a 的正确坑位（排序后的位置）为 j，b 的正确坑位为 i，那么 a 和应该交换。

所以，思路是保留原数组，然后在进行排序。

思路分析

尝试以图论的角度来分析，把每个瓶子看成一个点。每个瓶子向它应该在的位置的瓶子结点连一条边。如下图：
image.png

  1. 3原本的位置是3，而3位置被2号瓶子占有，所以3号瓶子应该连接2号瓶子。
  2. 我们会发现，所有点的出度和入度都为1，所有图都是由数个环组成的；
  3. 我们最终期望的样子是变成5个环；

对于交换有两种情况：

  1. 交换同一个环中的两个点，会裂变成两个独立的环；
  2. 交换不同环中的两个点，会合并两个环；

假设一开始，我们构造出了 n 个环，最后我们需要裂变成 k 个环，那么只需要 n - k 次操作就可以实现了。

执行流程设计

暴力

  1. 备份原数组；
  2. 对 backup 进行排序；
  3. 遍历原数组，如果发现有一个数不在其位置上，就在排序后的数组中找到对应的位置。（通过这个数，找到本来的位置，本来的位置就是这个数的值 a[i]，再通过这个位置 i 遍历 a 数组找到应该交换的数 b[i]）；

图论

  1. 构造环，得出一开始环的个数 cnt；
  2. 最后的答案就为 n - cnt；

总结

代码实现

图论

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

const int N = 1e4 + 10;
int n, cnt;
bool st[N];
int a[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    for (int i = 1; i <= n; i++) {
        if (st[i]) continue;
        cnt++;
        for (int j = i; !st[j]; j = a[j]) {
            st[j] = true;
        }
    }
    
    printf("%d", n - cnt);
    return 0;
}