做网站的收入来源/优化推荐

交换瓶子

题目描述

有N个瓶子，编号 1 ~ N，放在架子上。
比如有5个瓶子：2 1 3 5 4，要求每次拿起2个瓶子，交换它们的位置。
经过若干次后，使得瓶子的序号为：1 2 3 4 5
对于这么简单的情况，显然，至少需要交换2次就可以复位。
如果瓶子更多呢？你可以通过编程来解决。

输入

输入存在多组测试数据，对于每组测试数据：
第一行: 一个正整数N（N<10000）, 表示瓶子的数目
第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。

输出

对于每组测试数据输出一行，包含一个正整数表示答案

样例输入 Copy

5
3 1 2 5 4
5
5 4 3 2 1

样例输出 Copy

3
2

代码

思路在代码里面

#include<iostream>
#include<stdio.h>
using namespace std;
/*因为N个瓶子的编号就是1~N，所以每个瓶子本来应该在的位置就是自身编号的位置。我们要做的就是从第一个数开始判断当前瓶子是否在它本来的位置，如果不在则和它本来位置上的瓶子进行交换。复杂度O(N) 
*/
int a[10005];// a[]用来存当前数列的瓶子
int b[10005];// b[]用来存储i号瓶子的位置 
int main(){int N;int id;int sum;int id1,id2;//id1，id2为两个瓶子的编号 int pos1,pos2;//需要交换的两个瓶子的位置 while(scanf("%d",&N)!=EOF){for(int i=1;i<=N;i++){cin>>id;a[i]=id; //把当前瓶子排放顺序放入a[]数组中b[id]=i; //把编号为id的瓶子当前所在的位置存储到b[]数组中 }/*53 1 2 5 4a[1]=3; a[2]=1 a[3]=2 a[4]=5 a[5]b[3]=1; b[1]=2 b[2]=3 b[5]=4 b[4]=5 */ sum=0;//初始化交换次数for(int i=1;i<=N;i++){//如果当前位置瓶子的编号正好等于当前位置的序号，说明这个瓶子在它本来的位置，直接跳过本次循环 if(a[i] == i) continue; //到这一步，说明当前位置瓶子不在它本来应该在的位置，需要和它本来的位置上的瓶子交换//此时的i表示第i个位置，a[i]表示第i个位置瓶子的编号。//第i个位置应该存放的是编号为i的瓶子，但是编号为i的瓶子在编号为a[i]的瓶子的位置上 //b[a[i]]表示第i个位置瓶子它本来应该在的位置。//所以此时需要让id1指向a[i]这个瓶子，pos1指向第i个位置id1=a[i]; //获取当前位置存放的瓶子的编号 pos1=i; //当前所在位置 //pos2指向编号为a[i]的瓶子本来应该在的位置,id2指向编号为i的瓶子id2=i;   pos2=b[i];  //找到i号瓶子所在的位置 sum++;//操作数+1；//交换操作，把 a[pos2]=id1;//瓶子2的位置（pos2）放瓶子1（id1） b[id1]=pos2;//瓶子1（id1）放到瓶子2的位置（pos2） //瓶子2放到瓶子1的位置 a[pos1]=id2;//瓶子1的位置放瓶子2 b[id2]=pos1;//瓶子2放到瓶子1的位置 } cout<<sum<<endl;}
}