题号：1908
讲道理，这个是我之前在洛谷上做的，今天突然看到逆序对这个问题，感觉很重要，然后就回洛谷翻评测记录把逆序对这道题找出来把代码贴到博客上。
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 | #include<string> #include<cstring> #include<algorithm> #include<cstdlib> #include<iostream> using namespace std; int n,arr[40005],arr_temp[40005]; int cnt; void MergeSort(int start,int end){//[start,end] if(start==end)return; MergeSort(start,(start+end)/2); MergeSort((start+end)/2+1,end); memcpy(arr_temp+start,arr+start,sizeof(int)*(end-start+1)); int ptr1=start,ptr2=(start+end)/2+1,ptr_main=start; while(ptr1<=(start+end)/2&&ptr2<=end){ if(arr_temp[ptr1]<arr_temp[ptr2]){ arr[ptr_main]=arr_temp[ptr1]; ptr1++; }else{ arr[ptr_main]=arr_temp[ptr2]; ptr2++; cnt+=(start+end)/2-ptr1+1; } ptr_main++; } for(;ptr1<=(start+end)/2;ptr1++){ arr[ptr_main]=arr_temp[ptr1]; ptr_main++; } for(;ptr2<=end;ptr2++){ arr[ptr_main]=arr_temp[ptr2]; ptr_main++; } } int main(){ ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++)cin>>arr[i]; MergeSort(1,n); cout<<cnt; } |
20180730更新：又写了一遍，再贴代码：
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 | #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> #include<string> #include<vector> #include<queue> #include<map> #include<functional> using namespace std; int n; int arr[40005]; int tmparr[40005], tmparr2[40005]; int rop = 0; void mergeSort(int l, int r) { if (l == r)return; int ls = l, le = (l + r) / 2, rs = (l + r) / 2 + 1, re = r; mergeSort(ls, le); mergeSort(rs, re); int lp = ls, rp = rs, cp = l; while (lp <= le && rp <= re) { if (tmparr[lp] < tmparr[rp])tmparr2[cp++] = tmparr[lp++]; else { tmparr2[cp++] = tmparr[rp++]; rop += le - lp +1; } } for (; lp <= le; lp++)tmparr2[cp++] = tmparr[lp]; for (; rp <= re; rp++)tmparr2[cp++] = tmparr[rp]; memcpy(tmparr + l, tmparr2 + l, sizeof(int)*(r - l + 1)); } int main() { ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i++)cin >> arr[i]; memcpy(tmparr, arr, sizeof(arr)); mergeSort(1, n); cout << rop; } |
20200409更新：题目更新了，数据加强了。做了小小改动。
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 | #include<iostream> #include<cstring> using namespace std; long long n; long long arr[500005]; long long tmparr[500005], tmparr2[500005]; long long rop = 0; void mergeSort(long long l, long long r) { if (l == r)return; long long ls = l, le = (l + r) / 2, rs = (l + r) / 2 + 1, re = r; mergeSort(ls, le); mergeSort(rs, re); long long lp = ls, rp = rs, cp = l; while (lp <= le && rp <= re) { if (tmparr[lp] <= tmparr[rp])tmparr2[cp++] = tmparr[lp++]; else { tmparr2[cp++] = tmparr[rp++]; rop += le - lp + 1; } } for (; lp <= le; lp++)tmparr2[cp++] = tmparr[lp]; for (; rp <= re; rp++)tmparr2[cp++] = tmparr[rp]; memcpy(tmparr + l, tmparr2 + l, sizeof(long long) * (r - l + 1)); } int main() { ios::sync_with_stdio(false); cin >> n; for (long long i = 1; i <= n; i++)cin >> arr[i]; memcpy(tmparr, arr, sizeof(arr)); mergeSort(1, n); cout << rop; } |