|
|
|
|
|
收集图书
|
||||
|
春树在中央图书馆做一份兼职工作。他的工作是收集那些被粗心的用户遗留在桌子上的书籍，然后将它们重新放到这些书在书架上原来的位置。为了高效地完成这个任务，春树将这些书收集起来，放在一个长长的由他专用的空书架上，然后将它们按编号排序。他把这些排好序的书放到一个手推车，绕着书架来回走，将这些书放到适当的位置。 对于春树来说，一个非常困难的任务是在他的专用书架上将一定数目的书按编号排序。他总是选出两本次序颠倒的书，交换它们，再选出两本次序颠倒的书，交换它们，重复这样的"选择－交换"，直到所有的书被排好序。当一本编号小的书在另一本编号大的书的右边时，我们称两本书"次序颠倒"。 你的任务是编写一个程序，用最少次数的交换将这些书按它们的编号从小到大排序。 输入 输入文件的第一行包含一个整数t，表示测试数据的数目。每一组数据用两行描述：第一行包含一个整数n，表示在春树自己书架上的书的数目，第二行包含一个n个正整数组成序列，序列中第I个整数是位于第i位的书的编号，假设所有的编号都不相同，且不超过10,000。N也不超过1000。 输出 你的程序要输出t个整数，第i个整数表示第i组测试数据要交换的次数。 Sample Input Output for the Sample Input 2 5 25 347 12 19 203 7 55 101 47 61 82 11 96 Output for the Sample Input 3 4 |
||||
| 网站导航
| 关于曙光 | 联系我们
| 请提意见 Copyright © FuJian Sunshine Educational Info. Co.,Ltd. 福建曙光教育资讯有限公司 版权所有 |