德布劳内yyds @ 2021-05-27 14:44:43

#include<bits/stdc++.h>
using namespace std;

int a[500004],b[500004],n;
long long ans;

void merge(int l,int r)
{
    //分解
    if(l==r)
        return ;
    int mid = (l+r)/2;
    merge(l,mid),merge(mid+1,r);

    //合并
    int i = l,j = mid+1,k = l;
    while(i<=mid && j<=r)
        if(a[i] <= a[j])
            b[k++] = a[j++];
        else
        {
            b[k++] = a[j++];
            ans+=mid-i+1;
        }   
    while(i <= mid)
    {
        b[k++] = a[i++];
    }
    while(j <= r)
    {
        b[k++] = a[j++];
    }
    for(int i =l;i<=r;++i)
    {
        a[i] = b[i]; 
    }
    return;
}

int main()
{
    scanf("%d",&n); 
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    merge(1,n);
    printf("%lld",ans);
    return 0;
}

by invincible_summer @ 2021-05-27 14:52:50

不是很懂

by invincible_summer @ 2021-05-27 14:53:00

@Kevin0306

by invincible_summer @ 2021-05-27 14:53:16

void Merge_Sort(int a[], int ans[], int began, int end) {
    if(began == end) return;
    int mid = (began + end) / 2;
    int began_first = began, began_second = (mid + 1), cnt = began;
    Merge_Sort(a, ans, began, mid);
    Merge_Sort(a, ans, mid+1, end);
    while(began_first <= mid && began_second <= end) {
        if(a[began_first] <= a[began_second]) ans[cnt++] = a[began_first++];
        else ans[cnt++] = a[began_second++], s += (mid - began_first + 1);
    }
    while(began_first <= mid) ans[cnt++] = a[began_first++];
    while(began_second <= end) ans[cnt++] = a[began_second++];
    for(int i = began; i <= end; i++) a[i] = ans[i];
}

by invincible_summer @ 2021-05-27 14:54:03

变量意义如名字，自已康康吧

by Melon_Musk @ 2021-05-27 14:55:19

看了一下

#include<bits/stdc++.h>
using namespace std;

int a[500004],b[500004],n;
long long ans;

void merge(int l,int r)
{
    //分解
    if(l==r)
        return ;
    int mid = (l+r)/2;
    merge(l,mid),merge(mid+1,r);

    //合并
    int i = l,j = mid+1,k = l;
    while(i<=mid && j<=r)
        if(a[i] <= a[j])
//            b[k++] = a[j++];  *这里是i++不是j++
            b[k++] = a[i++];   
        else
        {
            b[k++] = a[j++];
            ans+=mid-i+1;
        }   
    while(i <= mid)
    {
        b[k++] = a[i++];
    }
    while(j <= r)
    {
        b[k++] = a[j++];
    }
    for(int i =l;i<=r;++i)
    {
        a[i] = b[i]; 
    }
    return;
}

int main()
{
    scanf("%d",&n); 
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    merge(1,n);
    printf("%lld",ans);
    return 0;
}

by 德布劳内yyds @ 2021-05-27 14:55:32

谢谢，我理解一下