首页 > 代码库 > vjudge-Brainman(参谋)题目翻译

vjudge-Brainman(参谋)题目翻译

参谋

雷蒙德把他的哥哥查理气坏了。雷蒙德只需用一眼就能数出撒到地板上的246根牙签,他甚至可以这样数扑克。查理也想做这么酷的事情。他想以类似的任务击败他的兄弟。

 

问题

以下是查理的想法。给你n个数字。我们的目标是移动的数字,最终使数字有序。允许的唯一操作是交换两个相邻数。举例:

开始 2 8 0 3

交换 (2 8) 8 2 0 3

交换 (2 0) 8 0 2 3

交换 (2 3) 8 0 3 2

交换 (8 0) 0 8 3 2

交换 (8 3) 0 3 8 2

交换 (8 2) 0 3 2 8

交换 (3 2) 0 2 3 8

交换 (3 8) 0 2 8 3

交换 (8 3) 0 2 3 8 

So the sequence (2 8 0 3) can be sorted with nine swaps of adjacent numbers. However, it is even possible to sort it with three such swaps:

因此,序列(2 8 0 3)可以用九次交换来排序。不过,还可以通过三个这样的交换排序:

开始  : 2 8 0 3

交换  (8 0) 2 0 8 3

交换  (2 0) 0 2 8 3

交换  (8 3) 0 2 3 8

The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?Since Charlie does not have Raymond‘s mental capabilities, he decides to cheat. Here is where you come into play. He asks you to write a computer program for him that answers the question. Rest assured he will pay a very good prize for it.

问题是:一个给定的序列需要交换的最小次数是多少?由于查理没有雷蒙德的本事,他决定作弊。这需要你的才能。他让你给他写一个计算机程序来回答这个问题。请放心,他会为此付出很高的奖赏。
//奖赏:100000000%10枚金币。

输入

第一行是序列的数量。

对于每一个序列,给出序列的长度N(1 < = N < = 1000)的行,然后是序列的N个元素 (-1000000,1000000)。各个数字之间由单个空格分隔。

输出

每一个序列从单独一行“Scenario # i:”开始输出,然后打印相邻数字的最小数量交换。用空行终止该序列的输出,然后按上述要求输出下一序列。

 

样例输入

4

4 2 8 0 3

10 0 1 2 3 4 5 6 7 8 9

6 -42 23 6 28 -100 65537

5 0 0 0 0 0

样例输出

Scenario #1:

3

 

Scenario #2:

0

 

Scenario #3:

5

 

Scenario #4:

0

//并没有题解,因为吾很懒:P

vjudge-Brainman(参谋)题目翻译