openjudge4.6贪心算法676:Sorting by Swapping_算法

题目

676:sorting by swapping
描述
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.
输入
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.
输出
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.
样例输入
2
3
1 2 3
5
2 3 5 4 1
样例输出
0
3

大意

` 没看太清，大概是从两头对调，完成排序。求最少对调次数。

思路

2 3 5 4 1
1 3 5 4 2
1 3 2 4 5
1 2 3 4 5
`从左遍历每个数，找剩下数中最小的，如果比当前是还小就交换，并记住交换次数。

数据结构

` 用结构体记住剩下数中最小数和最小数的位置。

代码

`#include <bits/stdc++.h>
using namespace std;
int t,n,d[10001];
struct node{
int id,x;
};
void view(){
cout<<“显示”<<endl;
cout<<“序号\t”;for(int i=1;i<=n;i++)cout<<i<<“\t”;cout<<endl;
cout<<“数据\t”;for(int i=1;i<=n;i++)cout<<d[i]<<“\t”;cout<<endl;
}
int main(){
//freopen(“in.cpp”,“r”,stdin);
cin>>t;
while(t–){
int m=0;
cin>>n;
for(int i=1;i<=n;i++)cin>>d[i];
for(int i=1;i<=n;i++){//从左遍历每个数
node w=node{i,d[i]};//结构体存最小数，开始是当前数
for(int j=i+1;j<=n;j++)//跟剩下的数比较
if(w.x>d[j])w.x=d[j],w.id=j;//如果比最小数还小，就是最小数
if(i!=w.id){//跟当前数不一样就交换
swap(d[i],d[w.id]);m++;
}
//view();
}
cout<<m<<endl;
}
return 0;
}