题目：给出一个正整数序列，使用swap(0,)的方式使其变为递增序列，求调用swap(0,)的次数
例如：对于序列{4, 0, 2, 1, 3}，我们可以如下：
Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}
因此，输出为3。
分析：
主体思想：
首先，如果数本身已经在正确位置，那它就不需要参与移动了（比如上例中的2），因此我们观察一下剩下的4个数：
image
可以发现除了2，其他数字和索引可以组成一个链条：4—0—1—3—4，而使用swap(0,*)也正是按照这样的顺序：
Swap(0, 1) => {4, 1, 2, 0, 3} ，将1送回本位，此时链条为0—3—4—0
Swap(0, 3) => {4, 1, 2, 3, 0} ，将3送回本位，此时链条为0—4—0
Swap(0, 4) => {0, 1, 2, 3, 4}，将4送回本位，此时无链条
因此，可以模拟这个过程，来解这道题（如算法笔记中的解法），但也可以从另一个角度出发，一共有5个数，除去不需要参与移动的2，还剩4个数，他们组成了一个链条，解开链条需要移动4-1=3，因此需要移动的次数的计算方法是5-1(不需要移动的一个数)-1(一条链条)=3。在此基础上，考虑以下情况：
- 组成两个链条：
image
组成了两个链条0—1—0，4—3—4。需要的swap如下：
Swap(0, 1) => {0, 1, 2, 4, 3} ，将1送回本位，解开链条1，此时链条为4—3—4
Swap(0, 3) => {3, 1, 2, 4, 0} ，0参与第2条链条，此时链条为3—0—4—3
Swap(0, 4) => {3, 1, 2, 0, 4} ，将4送回本位，此时链条为3—0—3
Swap(0, 3) => {0, 1, 2, 3, 4} ，将3送回本位，此时无链条
可以看出来，一共有两条链条，包含数的数量为2,2。对于第一条链条，需要移动的次数是2-1=1，对于第二条链条，由于0已经回到本位，不包含在链条中，因此额外把它引入，而引入后，第二条链条包含的数的数量就由2变成了3，因此需要移动的次数是2+1(移动0进入链条)+1（多一个数0）-1（解开链条）=3，即对于第二条链条而言，+1-1抵消，最早还是2+1=3，因此两条链条需要的总的次数是5-1(不需要移动的一个数)-1(第一条链条)+1(第二条链条)=4
- 组成三个链条：
image
组成了三个链条0—1—0，4—3—4，6—5—6需要的swap如下：
Swap(0, 1) => {0, 1, 2, 4, 3, 6, 5} ，将1送回本位，解开链条1，此时链条为4—3—4，6—5—6
Swap(0, 3) => {3, 1, 2, 4, 0, 6, 5} ，0参与第2条链条，此时链条为3—0—4—3，6—5—6
Swap(0, 4) => {3, 1, 2, 0, 4, 6, 5} ，将4送回本位，此时链条为3—0—3，6—5—6
Swap(0, 3) => {0, 1, 2, 3, 4, 6, 5} ，将3送回本位，解开链条2，此时链条为6—5—6
Swap(0, 3) => {6, 1, 2, 3, 4, 0, 5} ，0参与第3条链条，此时链条为6—0—5—5
Swap(0, 4) => {6, 1, 2, 3, 4, 5, 0} ，将4送回本位，此时链条为6—0—6
Swap(0, 3) => {0, 1, 2, 3, 4, 6, 5} ，将3送回本位，解开链条3，此时无链条
与两条链条的情况类似，第三条链条与第二条链条的处理方法相同，因此总次数为7-1(不需要移动的一个数)-1(第一条链条)+1(第二条链条)+1(第三条链条)=7
因此如果有n个需要移动的数，则最终需要移动的次数为：
一条链条：n-1
两条链条：n-1+1
三条链条：n-1+1+1
...
m条链条：n-1+（m-1）个1=n+m-2
因此，代码如下：
#include<cstdio>
int main(){
int n,ans;
scanf("%d",&n);
int a[n];
ans=n;//总数量
int flag[n]={false};//标记是否被移动过了
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
if(a[i]==i){//如果某个数不需要移动
flag[i]=true;//标记一下
ans--;//总次数-1
}
}
int count=0;
for(int i=0;i<n;i++){
if(!flag[i]){
flag[i]=true;//标记已经被移动过了
int start=i;//存储链条开头
int next=a[i];//沿着链条往下走
count++;
while(next!=start){//将链条里的所有数全都标记
flag[next]=true;
next=a[next];
}
}
}
printf("%d\n",ans+count-2);
return 0;
}
但是，这样并不能通过所有的测试案例，为什么呢？
如果一开始0就已经在本位上了怎么办？
image
这种情况下，即使是一条链条，也需要将0引入，造成一条链条的情况下，最终需要移动的次数由n-1变成了n+1
两条链条则变成了n+2，m条链条变成了n+m
因此代码改为：
#include<cstdio>
int main(){
int n,ans;
scanf("%d",&n);
int a[n];
ans=n;
int flag[n]={false};
int flag0=0;//记录0是否一开始就在本位
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
if(a[i]==i){
flag[i]=true;
ans--;
}
}
int count=0;
if(flag[0]){
flag0=1;
}
for(int i=0;i<n;i++){
if(!flag[i]){
flag[i]=true;
int start=i;
int next=a[i];
count++;
while(next!=start){
flag[next]=true;
next=a[next];
}
}
}
//如果0一开始在本位,flag0=1，表达式为ans+count
//如果0一开始不在本位,flag0=0，表达式为ans+count-2
printf("%d\n",ans+count-2+flag0*2);
return 0;
}
网友评论