最少的交换
题目描述
现在给你一个由n个互不相同的整数组成的序列，现在要求你任意交换相邻的两个数字，使序列成为升序序列，请问最少的交换次数是多少？
输入
输入包含多组测试数据。每组输入第一行是一个正整数n（n<500000），表示序列的长度，当n=0时。
接下来的n行，每行一个整数a[i]（0<=a[i]<=999999999），表示序列中第i个元素。
输出
对于每组输入，输出使得所给序列升序的最少交换次数。
样例输入
5
9
1
0
5
4
3
1
2
3
0
样例输出
6
0
1 #include<iostream>
2 using namespace std;
3 int x[
500050],b[
500050];
//归并排序过程中累加所有逆序数
4 long long num;
//注意交换次数类型
5 void Merge(
int data[],
int low,
int mid,
int high)
6 {
7 int i = low, j = mid +
1, k =
low;
8 while (i <= mid && j <=
high)
9 {
10 if (data[i] <=
data[j])
11 b[k++] = data[i++
];
12 else
13 {
14 num += j -
k;
15 b[k++] = data[j++
];
16 }
17 }
18 while (i <=
mid)
19 b[k++] = data[i++
];
20 while (j <=
high)
21 b[k++] = data[j++
];
22 for (i = low; i <= high; i++, k++
)
23 data[i] =
b[i];
24 }
25 void MergeSort(
int data[],
int low,
int high)
26 {
27 if (low<
high)
28 {
29 int mid = (low + high) /
2;
30 MergeSort(data, low, mid);
31 MergeSort(data, mid +
1, high);
32 Merge(data, low, mid, high);
33 }
34 }
35
36 int main()
37 {
38 int n;
39 while (cin >> n&&
n)
40 {
41 for (
int i =
0; i < n; i++
)
42 {
43 cin >>
x[i];
44 }
45 num =
0;
46 MergeSort(x,
0, n -
1);
47 cout << num <<
endl;
48 }
49 return 0;
50 }
51
52
53
54 #include<iostream>
55 using namespace std;
56 int a[
500010],b[
500010];
57 long long int count;
58 void Merge(
int start,
int mid,
int end)
59 {
60 int i=start,j=mid+
1,tip=
start;
61 while(i<=mid&&j<=
end)
62 {
63 if(a[i]<=a[j]) b[tip++]=a[i++
];
64 else
65 count+=(j-tip),b[tip++]=a[j++
];
66 }
67 while(i<=mid) b[tip++]=a[i++
];
68 while(j<=end) b[tip++]=a[j++
];
69 for(
int i=start;i<=end;i++
)
70 a[i]=
b[i];
71 }
72 void MergeSort(
int start,
int end)
73 {
74 if(start<
end)
75 {
76 int mid=(start+end)/
2;
77 MergeSort(start,mid);
78 MergeSort(mid+
1,end);
79 Merge(start,mid,end);
80 }
81 }
82 int main()
83 {
84 int n;
85 while(cin>>n&&
n)
86 {
87 for(
int i=
1;i<=n;i++
)
88 cin>>
a[i];
89 count=
0;
90 MergeSort(
1,n);
91 cout<<count<<
endl;
92 }
93 return 0;
94 }
View Code
转载于:https://www.cnblogs.com/qing123tian/p/11107502.html
相关资源：数据结构—成绩单生成器
