2024年5月17日发(作者：赏远骞)
Sorting by Swapping
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 5760 Accepted: 3033
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
参考了别人的算法。。
{3 ,7 ,1 ,6 ,2 ,4 ,8 ,5 }再和标准序列
{1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }比较
找出其中所有的"环"
这里的"环"就是指它们互相交换之后能成为标准序列的最小集合
比如 这里{1,3}是一个"环", {7,2,5,8}是一个"环"。
具体找法很简单 首先确定一个不在已找出"环"中的数字
例如第一次从3开始,3对应标准序列的1 再找1对应的标准序列3 3回到了开
始的数字 那么这个环就是{1,3}
第二次从7开始,7->2 2->5 5->8 8->7 所以第二个环是{7,2,5,8}
第三个环是{6,4}
这样所有的数字都在环中了
交换的次数=(数字总数-环数)=8-3=5
代码：
#include
int main()
{
int m,n,i,j,k,a[10010]={0},b[10010]={0},sum;
scanf("%d",&m);
while(m--)
{ scanf("%d",&n);
sum=0;
for(i=0;i for(i=0;i for(i=0;i { j=i; if(b[i]!=0) { while(b[i]!=a[j]) { j=a[j]-1; b[j]=0; } sum++; } } printf("%dn",n-sum); } return 0; } 2024年5月17日发(作者：赏远骞)
Sorting by Swapping
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 5760 Accepted: 3033
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
参考了别人的算法。。
{3 ,7 ,1 ,6 ,2 ,4 ,8 ,5 }再和标准序列
{1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }比较
找出其中所有的"环"
这里的"环"就是指它们互相交换之后能成为标准序列的最小集合
比如 这里{1,3}是一个"环", {7,2,5,8}是一个"环"。
具体找法很简单 首先确定一个不在已找出"环"中的数字
例如第一次从3开始,3对应标准序列的1 再找1对应的标准序列3 3回到了开
始的数字 那么这个环就是{1,3}
第二次从7开始,7->2 2->5 5->8 8->7 所以第二个环是{7,2,5,8}
第三个环是{6,4}
这样所有的数字都在环中了
交换的次数=(数字总数-环数)=8-3=5
代码：
#include
int main()
{
int m,n,i,j,k,a[10010]={0},b[10010]={0},sum;
scanf("%d",&m);
while(m--)
{ scanf("%d",&n);
sum=0;
for(i=0;i for(i=0;i for(i=0;i { j=i; if(b[i]!=0) { while(b[i]!=a[j]) { j=a[j]-1; b[j]=0; } sum++; } } printf("%dn",n-sum); } return 0; }