首页 > 代码库 > UVA 331 交换的方案数
UVA 331 交换的方案数
题意:交换一个数组的相邻两个元素可以达到对数组排序的功能,类似于冒泡排序,但交换的方案可能不止一种。比如说数组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.\n", ans, ++T );61 }62 return 0;63 }
UVA 331 交换的方案数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。