交换瓶子 | CYY's Blog

题目来源

https://www.acwing.com/problem/content/1226/

题目

有 N 个瓶子，编号 1∼N，放在架子上。

比如有 5 个瓶子：

2 1 3 5 4

要求每次拿起 2 个瓶子，交换它们的位置。

经过若干次后，使得瓶子的序号为：

1 2 3 4 5

对于这么简单的情况，显然，至少需要交换 2 次就可以复位。

如果瓶子更多呢？你可以通过编程来解决。

输入格式

第一行包含一个整数 N，表示瓶子数量。

第二行包含 N 个整数，表示瓶子目前的排列状况。

输出格式

输出一个正整数，表示至少交换多少次，才能完成排序。

数据范围

1≤N≤10000

输入样例1

1 2	5 3 1 2 5 4

输出样例1

输入样例2

1 2	5 5 4 3 2 1

输出样例2

AC代码

贪心

用贪心的思想：

根据题意可知，所给一个N，那么就必然包含1-n这n个数字，还要求递增，因此其数字应该与下标对应（下标0不存储数据），意思就是数字1必须在1这个下标位置，数字2必须在2这个下标位置，所以我们直接对元素互换。互换次数就是所求答案

样例分析：

3，1，2，5，4 第一个数字是3，它本应该在下标为3的位置，但是却在下标为1这个位置，无论我们怎么交换，数字3最终会在3这个位置，最终结果一样，我们怎样保证最少次交换次数让其在它本应该在的位置呢？显然我们直接将3放在下标3的位置，与原来下标3位置的元素进行交换即可，所以3和2交换，第一位是2，2又和1交换，现在数组变成1，2，3，5，4，我们继续遍历到5，然后5和4进行交换。总交换次数3

#include <iostream>
using namespace std;
const int MAX = 10004;
int main(){
    int n,res = 0;
    int num[MAX];
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>num[i];
    //枚举如果第i位的值是否在其所在位置
    for(int i = 1; i <= n; i++){
        int temp;
        while(num[i] != i){
            //不在就交换位置
            temp = num[i];
            num[i] = num[temp];
            num[temp] = temp;
            res++;
        }
    }
    cout<<res<<endl;
    return 0;
}

图

可以将数组转换成图，我们把以交换顺序为边作图（上面那种方法分析了实际上就是数字应该与其下标对应，所以是3就要和下标为3的元素互换），直接样例分析：3，1，2，5，4：3->2->1>3这是一个环，5->4->5这是一个环。我们最终要将数组搞成升序也就是：1，2，3，4，5，转换为图其实就是1->1,2->2,3->3,4->4,5->5。也就是从上面2个环转换成5个自环。对于一个环（3，1，2），我们任意交换一对（1，2）线性结果为3，2，1，环为3–>1->3,2->2.1个环裂成了2个环，再交换一次3->1->3这个环，又分一个环出来，最终（3，1，2）这个三个元素组成的环操作两次变成全自环。对于（5，4）这两个元素组成的环，交换一次即可。对于一个环，有3个元素，操作2次，有2个元素操作1次。综合来说对于两个环，有3+2五个元素，操作了2+1次，5个元素操作了3次，多举几个例子就可以得到，元素数量-操作次数=环数，所以，元素数量-环数 =操作次数，因此我们只需要看有多少个环就行

#include <iostream>
using namespace std;
const int MAX = 10004;
bool v[MAX];//记录是否遍历过
int num[MAX];
int main(){
    int n,res = 0;
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>num[i];
    
    for(int i = 1; i <= n; i++){
        if(!v[num[i]]){	//如果第i个位置的数组没有遍历则就是一个新环
            res++;//环数++
            for(int j = num[i]; !v[j]; j = num[j]){
                v[j] = true;	//循环遍历，遍历的元素设为t
            }
        }
    }
    cout<<n-res<<endl;
    return 0;
}