题目：Given a permutation of numbers from 1 to n, we can always get the sequence 1, 2, 3, ..., n by swapping pairs of numbers. For example, if the initial sequence is 2, 3, 5, 4, 1, we can sort them in the following way: 2 3 5 4 1 1 3 5 4 2 1 3 2 4 5 1 2 3 4 5 Here three swaps have been used. The problem is, given a specific permutation, how many swaps we needs to take at least. 我写的程序： #include "stdafx.h"#include <iostream>using namespace std;int main(){int n,i=1,j,m,count,temp;int s[10001];cin>>n;for(;n!=0;n--){ cin>>m;  count=0;   for(j=1;j<=m;j++)     cin>>s[j];   for(i=1;i<=m;i++)    while(s[i]!=i)   {j=s[i];temp=s[i];s[i]=s[j];s[j]=temp;count++;}   cout<<count<<endl;}return 0;} 运行结果虽然正确，但是老超时，效率不高！在网上看到别人的程序，效率要提高很多： #include<stdio.h>int main(){        int n,m,i,j,k,t;        short p[10001],q[10001];        scanf("%d",&n);        for (i=0;i<n;i++)        {                scanf("%d",&m);                for (j=1;j<=m;j++)                {                        scanf("%d",&p[j]);                        q[p[j]]=j;                }                t=0;                for (j=1;j<=m;j++)                {                        if (p[j]!=j)                        {                                t++;                                p[q[j]]=p[j];                                q[p[j]]=q[j];                        }                }                printf("%d\n",t);        }        return 0;}

评论