题意：交换一个数组的相邻两个元素可以达到对数组排序的功能，类似于冒泡排序，但交换的方案可能不止一种。比如说数组A【3】为3,2,1，要想排为1,2,3，可以先交换位置1和2的元素（数组变为2，3，1），然后交换位置2和3的元素（变为2，1，3），最后交换位置1和2的（变为1，2，3），此为方案一，具体可以用1,2,1（数字即每次交换的第一个数的位置）来描述。当然还可以先交换位置2和3（312），然后交换位置1和2（132）最后交换位置2和3（123），如上的描述方法便是2,1,2，此为方案二。当然这样的方案是无穷多的，比如1，1，2，1，2同样可以实现排序，但这种情况下前两次交换是在做无用功，不是移动次数最小的方案。此题要求出移动次数最少的方案有多少个，如例子中的情况就只有2种方案。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cctype> 4 #include <cstring> 5 #include <cmath> 6 #include <ctime> 7 #include <string> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <algorithm> 12 #include <iostream> 13 using namespace std; 14 typedef long long ll; 15 const int NO = 10000 + 10; 16 int a[NO]; 17 int n, ans; 18 19 inline bool judge() 20 { 21 for( int i = 1; i < n; ++i ) 22 if( a[i] > a[i+1] ) 23 return false; 24 return true; 25 } 26 27 int Swap( int i, int j ) 28 { 29 int t = a[i]; 30 a[i] = a[j]; 31 a[j] = t; 32 } 33 34 void dfs() 35 { 36 if( judge() ) 37 { 38 ++ans; 39 return; 40 } 41 for( int i = 1; i < n; ++i ) 42 if( a[i] > a[i+1] ) 43 { 44 Swap( i, i+1 ); 45 dfs(); 46 Swap( i, i+1 ); 47 } 48 } 49 50 int main() 51 { 52 int T = 0; 53 while( ~scanf( "%d", &n ) && n ) 54 { 55 for( int i = 1; i <= n; ++i ) 56 scanf( "%d", &a[i] ); 57 ans = 0; 58 if( !judge() ) 59 dfs(); 60 printf( "There are %d swap maps for input data set %d. ", ans, ++T ); 61 } 62 return 0; 63 }