-
Notifications
You must be signed in to change notification settings - Fork 2
/
main.cpp
122 lines (116 loc) · 2.78 KB
/
main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<iostream>
#include<vector>
using namespace std;
//int InversePairs(const vector<int>& v)
//{
// int count=0;
// int i,j;
// for(i=0;i<v.size();++i)
// {
// for(j=i;j<v.size();++j)
// {
// if(v[i]>v[j])
// count++;
// }
// }
// return count;
//}
void Merge(vector<int>& v,int left,int mid,int right,vector<int>& tmp,int& count)
{
int i=mid,j=right,k=right;
while(i>=left && j>mid)
{
if(v[i]<v[j])
tmp[k--]=v[j--];
else
{
tmp[k--]=v[i--];
count+=(j-mid);
}
}
while(i>=left)
tmp[k--]=v[i--];
while(j>mid)
tmp[k--]=v[j--];
for(i=left;i<=right;++i)
{
v[i]=tmp[i];
}
}
void MergeSort(vector<int>& v,int left,int right,vector<int>& tmp,int& count)
{
if(right-left>1)
{
int mid=left+(right-left)/2;
MergeSort(v,left,mid,tmp,count);
MergeSort(v,mid+1,right,tmp,count);
Merge(v,left,mid,right,tmp,count);
}
else
{
Merge(v,left,left,right,tmp,count);
}
}
int InversePairs(vector<int> v)
{
int count=0;
vector<int> tmp;
tmp.resize(v.size());
MergeSort(v,0,v.size()-1,tmp,count);
return count;
}
//------测试代码-----
void test()
{
vector<int> v[6];
int arr0[]={7,5,6,4};
int arr1[]={1,2,3,4,5,6,7,8,9};
int arr2[]={9,8,7,6,5,4,3,2,1};
int arr3[]={5,6};
int arr4[]={6,5};
int arr5[]={5};
int i,j;
for(i=0;i<6;++i)
{
switch(i)
{
case 0:
for(j=0;j<sizeof(arr0)/sizeof(arr0[0]);++j)
v[i].push_back(arr0[j]);
cout<<InversePairs(v[i])<<endl;
break;
case 1:
for(j=0;j<sizeof(arr1)/sizeof(arr1[0]);++j)
v[i].push_back(arr1[j]);
cout<<InversePairs(v[i])<<endl;
break;
case 2:
for(j=0;j<sizeof(arr2)/sizeof(arr2[0]);++j)
v[i].push_back(arr2[j]);
cout<<InversePairs(v[i])<<endl;
break;
case 3:
for(j=0;j<sizeof(arr3)/sizeof(arr3[0]);++j)
v[i].push_back(arr3[j]);
cout<<InversePairs(v[i])<<endl;
break;
case 4:
for(j=0;j<sizeof(arr4)/sizeof(arr4[0]);++j)
v[i].push_back(arr4[j]);
cout<<InversePairs(v[i])<<endl;
break;
case 5:
for(j=0;j<sizeof(arr5)/sizeof(arr5[0]);++j)
v[i].push_back(arr5[j]);
cout<<InversePairs(v[i])<<endl;
break;
default:
break;
}
}
}
int main()
{
test();
return 0;
}