# 一个简单的ACM题目，请那位大哥帮忙？解决办法

www.MyException.Cn  网友分享于：2013-02-17  浏览：9次

Sorting   by   Swapping
Time   Limit:1000MS     Memory   Limit:10000K
Total   Submit:2701   Accepted:1457

Description
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.

Input
The   first   line   contains   a   single   integer   t   (1   <=   t   <=   20)   that   indicates   the   number   of   test   cases.   Then   follow   the   t   cases.   Each   case   contains   two   lines.   The   first   line   contains   the   integer   n   (1   <=   n   <=   10000),   and   the   second   line   gives   the   initial   permutation.

Output
For   each   test   case,   the   output   will   be   only   one   integer,   which   is   the   least   number   of   swaps   needed   to   get   the   sequence   1,   2,   3,   ...,   n   from   the   initial   permutation.

Sample   Input

2
3
1   2   3
5
2   3   5   4   1

Sample   Output

0
3

#include   <iostream>
using   namespace   std;
int   main()
{
int   a[10000],e[20];
int   t,n,g,h,s;
cin   > >   t;
for(int   k=0;k <t;k++)
{
cin   > >   n;
for(int   d=0;d <n;d++)
cin   > >   a[d];
for(int   i=0,d=0;d <n;d++)
{
s=d;
for(h=d+1;h <n;h++)
{
if(a[s]> a[h])s=h;
}
if(s!=d)
{
g   =   a[s];
a[s]   =   a[d];
a[d]   =   g;
i++;
}
e[k]   =   i;