算法 数据结构 c++ 职场和发展 蓝桥杯：交换瓶子

题目

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

比如有5个瓶子： 2 1 3 5 4

要求每次拿起2个瓶子，交换它们的位置。 经过若干次后，使得瓶子的序号为： 1 2 3 4 5

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

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

输入格式为两行： 第一行: 一个正整数N（N<10000）, 表示瓶子的数目 第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。

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

输入 5 3 1 2 5 4

输出 3

思路

使用swap(a[i],a[a[i]])来交换，把a[i]移动到正确的索引i位置

代码

#include

using namespace std;

int a[10005],n,ans;

int main()

{

cin>>n;

for(int i = 1;i <= n;i++){

cin>>a[i];

}

for(int i = 1;i <= n;i++)

{

while(a[i] != i){

swap(a[i],a[a[i]]);//把a[i]移动到正确的索引i位置

ans++;

}

}

cout<

return 0;

}

总结：swap(a[i],a[a[i]])用来计算逆置数组的最小交换次数，称为“洗牌算法”

参考链接

 您阅读本篇文章共花了：