UVa 299 Train Swapping:冒泡排序的次数

299 - Train Swapping

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=98&page=show_problem&problem=235

At an old railway station, you may still encounter one of the last remaining ``train swappers''. A train swapper is an employee of the railroad, whose sole job it is to rearrange the carriages of trains.

Once the carriages are arranged in the optimal order, all the train driver has to do, is drop the carriages off, one by one, at the stations for which the load is meant.

The title ``train swapper'' stems from the first person who performed this task, at a station close to a railway bridge. Instead of opening up vertically, the bridge rotated around a pillar in the center of the river. After rotating the bridge 90 degrees, boats could pass left or right.

The first train swapper had discovered that the bridge could be operated with at most two carriages on it. By rotating the bridge 180 degrees, the carriages switched place, allowing him to rearrange the carriages (as a side effect, the carriages then faced the opposite direction, but train carriages can move either way, so who cares).

Now that almost all train swappers have died out, the railway company would like to automate their operation. Part of the program to be developed, is a routine which decides for a given train the least number of swaps of two adjacent carriages necessary to order the train. Your assignment is to create that routine.

Input Specification

The input contains on the first line the number of test cases (N). Each test case consists of two input lines. The first line of a test case contains an integer L, determining the length of the train (

). The second line of a test case contains a permutation of the numbers 1 through L, indicating the current order of the carriages. The carriages should be ordered such that carriage 1 comes first, then 2, etc. with carriage L coming last.

Output Specification

For each test case output the sentence: 'Optimal train swapping takes S swaps.' where S is an integer.

Example Input

3
3
1 3 2
4
4 3 2 1
2
2 1

Example Output

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.

冒泡排序的次数。

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索train
, bridge
, test
, swap 排序
, of
, The
first
train、party train、summertrain、trainline、train to busan,以便于您获取更多的相关知识。

时间: 2024-10-28 13:27:22

UVa 299 Train Swapping:冒泡排序的次数的相关文章

UVa 331:Mapping the Swaps

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=267 题目类型: 回溯 原题: Sorting an array can be done by swapping certain pairs of adjacent entries in the array. This is the fundame

UVa 10602

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1543 类型:贪心 原题: Company Macrohard has released it's new version of editor Nottoobad, which can understand a few voice commands.

[数据结构] 冒泡排序

概述 冒泡排序通过重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来,直到没有再需要交换的元素为止(对n个项目需要O(n^2)的比较次数).这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 实现步骤 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对.这步做完后,最后的元素会是最大的数. 针对所有的元素重复以上的步骤,除了最后一个. 持续每次对越来越少的元素重复上面的步骤,直

内部排序算法:冒泡排序

基本思想 将被排序的记录数组R[0..n-1]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡.根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其 向上"飘浮".如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止. 具体过程,如下所示: 初始状态:R[0..n-1]为无序区. 第一趟扫描:从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下.重者 在上,则交换二者的位置,即依次比较(R[n-1], R[n-2]).(R

冒泡排序算法

简化版的桶排序不仅仅有上一节所遗留的问题,更要命的是:它非常浪费空间!例如需要排序数的范围是0~2100000000之间,那你则需要申请2100000001个变量,也就是说要写成int a[2100000001].因为我们需要用2100000001个"桶"来存储0~2100000000之间每一个数出现的次数.即便只给你5个数进行排序(例如这5个数是1,1912345678,2100000000,18000000和912345678),你也仍然需要2100000001个"桶&q

UVa 10716: Evil Straw Warts Live

[链接] http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1657 [原题] A palindrome is a string of symbols that is equal to itself when reversed. Given an input string, not necessarily a

UVa 558:Wormholes (求负回路)

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=499&mosmsg=Submission+received+with+ID+10614453 题目: Wormholes In the year 2163, wormholes were discovered. A wormhole is a sub

UVa 10557:XYZZY

题目链接 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=1498 题目类型: 搜索 题目: The prototypical computer adventure game, first designed by Will Crowther on the PDP-10 in the mid-1970s as

UVa 10129:Play on Words, 欧拉道路

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=1070 题目类型: 欧拉道路 题目: Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve