洛谷 逆序对

题号: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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注