频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
UVA Mapping the Swaps
2014-07-16 10:42:31         来源:u013840081的专栏  
收藏   我要投稿

题目如下:

Mapping the Swaps

Sorting an array can be done by swapping certain pairs of adjacent entriesin the array. This is the fundamental technique used in the well-knownbubble sort. If we list the identities of the pairs to be swapped, in thesequence they are to be swapped, we obtain what might be called a swap map.For example, suppose we wish to sort the array A whose elements are 3, 2,and 1 in that order. If the subscripts for this array are 1, 2, and 3,sorting the array can be accomplished by swapping A2 and A3, then swapping A1and A2, and finally swapping A2 and A3. If a pair is identified in a swapmap by indicating the subscript of the first element of the pair to beswapped, then this sorting process would be characterized with the swap map2 1 2.

It is instructive to note that there may be many ways in which swapping ofadjacent array entries can be used to sort an array. The previous array,containing 3 2 1, could also be sorted by swapping A1 and A2, then swappingA2 and A3, and finally swapping A1 and A2 again. The swap map that describesthis sorting sequence is 1 2 1.

For a given array, how many different swap maps exist? A little thoughtwill show that there are an infinite number of swap maps, since sequentialswapping of an arbitrary pair of elements will not change the order of the elements. Thus the swap map 1 1 1 2 1 will also leave our arrayelements in ascending order. But how many swap maps of minimum size willplace a given array in order? That is the question you are to answer in this problem.

Input

The input data will contain an arbitrary number of test cases, followed by asingle 0. Each test case will have a integer n that gives the size of anarray, and will be followed by the n integer values in the array.

Output

For each test case, print a message similar to those shown in thesample output below. In no test case will n be larger than 5.

Sample Input

2 9 7
2 12 50
3 3 2 1
3 9 1 5
0

Sample Output

There are 1 swap maps for input data set 1.
There are 0 swap maps for input data set 2.
There are 2 swap maps for input data set 3.
There are 1 swap maps for input data set 4.
求将一个数组排序的不同方法的个数,可以将数组相邻两数交换,要求交换的次数必须最少。其实只要不重复交换两个元素,交换的次数就是最少的。知道这一点后就可以直接回溯了。

AC的代码如下:


点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:HDU 1051: Wooden Sticks(贪心)
下一篇:hdu 1257 最少拦截系统
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站