tianxuyuan

待做

Sorting by Swapping
Time Limit:1000MS  Memory Limit:10000K
Total Submit:2515 Accepted:1374

Description
Given a permutation of numbers from 1 to n, we can always get the sequence 1, 2, 3, ..., n by swapping pairs of numbers. For example, if the initial sequence is 2, 3, 5, 4, 1, we can sort them in the following way:

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

Here three swaps have been used. The problem is, given a specific permutation, how many swaps we needs to take at least.


Input
The first line contains a single integer t (1 <= t <= 20) that indicates the number of test cases. Then follow the t cases. Each case contains two lines. The first line contains the integer n (1 <= n <= 10000), and the second line gives the initial permutation.

Output
For each test case, the output will be only one integer, which is the least number of swaps needed to get the sequence 1, 2, 3, ..., n from the initial permutation.

Sample Input


2
3
1 2 3
5
2 3 5 4 1

Sample Output


0
3

posted on 2007-05-05 11:17 田旭园 阅读(540) 评论(1)  编辑 收藏 引用

Feedback

# re: 待做 2007-05-06 10:28 Santa

其实就是求解逆序数的个数……
O(nlogn)时间内可以完成,参考归并排序……  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理