中国石油大学OJ – 排队

题目

乐乐的 n 位朋友都拥有唯一的一个编号,编号分别为 1 至 n。某天按到达的时间顺序又给了一个顺序号,此时发现顺序号与多数的朋友编号不一致。乐乐想:如果俩俩交换顺序号,使得每位朋友的编号与顺序号相同,则最少需要交换几次?

输入:
包含二行:
第一行只有一个正整数:n,表示乐乐朋友的人数
第二行共有 n 个正整数,分别表示按顺序到达的朋友编号

输出:
只有一行且只有一个正整数:最少的交换次数

对于 30%的数据, 1 <= n <= 100
对于 80%的数据, 1 <= n <= 10 000
对于 100%的数据, 1 <= n <= 100 000

样例

样例输入

5  
4 2 1 5 3

样例输出

3

解析

画一个这样的图:把所有位置不正确的数字与它正确的位置连一个箭头。

比如说样例,他应该是:

我们可以利用离散数学图论中的入度和出度来理解这件事情:

  1. 一个数字如果在正确的位置上,那不可能有箭头指向这个位置,这个位置也不可能有箭头指向别的位置,我就是我,不一样的自我。也就是说入度和出度是0;
  2. 如果他不在自己的位置上,那它肯定指向某一个别的位置,并且另外一个位置上的数字肯定想回来,所以也有一个箭头指向这个位置,所以入度和出度都是1。

这样在全局上来看,肯定会导致我们可以连成一个或者若干个有向环,比如上图是样例连成的一个有向环。
这里需要说明的是,两个有向环之间必然是独立的,不可能有两个有向环有公共点。这是因为我们按照上面的逻辑分析入度出度,入度和出度都是1,哪儿来的公共点,要是公共了,入度和出度不就大于1了嘛。

不难想象,对于某一个有n个节点的有向环,还原成原本的样子需要移动的最小次数是n-1次。可以找规律验证(想想的话也不难想,因为1~n-2次移动只是帮助一个数字走到了他应该去的地方,但是第n-1次移动一下子帮助了俩数字)。

问题转换为,求所给区间有多少个有向环,以及每个有向环有多少个节点。每个有向环节点数减一再累加起来就是答案了。

有向环怎么找?可以遍历迭代。先从4看,4位置不对,看看4号位置是谁,是5,还是不对,看看5号位置,是3,还是不对,看看3号位置,是1,还是不对,看看1号位置,哦,又回到4了,那这就是个环。很明显,这个过程非常迭代,通过迭代一定能找到一个完整的有向环(就是我自己试了试好像挺容易写错的2333)。

代码

#include<iostream>

#define rep(a, b, c) for(int a=b;a<=c;i++)
#define max(a, b) a>b?a:b

using namespace std;

typedef long long ll;
const int N = 1008611;

int n, nums[N];
bool f[N];

int cnt(int index) {
    int pos = nums[index];
    f[index] = true;
    f[pos] = true;

    int t = 1;
    while (pos != index) {
        pos = nums[pos];
        f[pos] = true;
        t++;
    }
    return t;
}

ll ans = 0;

int main() {
    cin >> n;
    rep(i, 1, n) cin >> nums[i];

    rep(i, 1, n) {
        if (nums[i] != i && !f[i]) {
            int r = cnt(i) - 1;
            ans += max(0, r);
        }
    }

    cout << ans << endl;

    return 0;
}
上一篇
下一篇