为什么我用归并有一半re了,50分

JSJ_WuYeHao @ 2024-11-08 09:05:28

#include <iostream>

using namespace std;

#define N 100010
typedef long long LL;
int arr[N];
int tmp[N];

LL merge_sort(int arr[],int l,int r) {
    if (l >= r) {
        return 0;
    }
    int mid = r + l >> 1;
    int k = 0; int i = l; int j = mid + 1;
    LL sum = 0;
    sum += merge_sort(arr, l, mid) + merge_sort(arr, mid + 1, r);
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j])tmp[k++] = arr[i++];
        else {
            sum += mid - i + 1;
            tmp[k++] = arr[j++];
        }
    }
    while(i <= mid)tmp[k++] = arr[i++];
    while(j <= r)tmp[k++] = arr[j++];
    for (i = l, j = 0; i <= r; i++, j++)arr[i] = tmp[j];
    return sum;
}
int main() {

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << merge_sort(arr,0,n-1) << endl;
    system("pause");

    return 0;
}

by gukecheng @ 2024-11-08 09:38:19

#include <iostream>

using namespace std;

#define N 500010
typedef long long LL;
int arr[N];
int tmp[N];

LL merge_sort(int arr[],int l,int r) {
    if (l >= r) {
        return 0;
    }
    int mid = r + l >> 1;
    int k = 0; int i = l; int j = mid + 1;
    LL sum = 0;
    sum += merge_sort(arr, l, mid) + merge_sort(arr, mid + 1, r);
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j])tmp[k++] = arr[i++];
        else {
            sum += mid - i + 1;
            tmp[k++] = arr[j++];
        }
    }
    while(i <= mid)tmp[k++] = arr[i++];
    while(j <= r)tmp[k++] = arr[j++];
    for (i = l, j = 0; i <= r; i++, j++)arr[i] = tmp[j];
    return sum;
}
int main() {

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << merge_sort(arr,0,n-1) << endl;
    system("pause");

    return 0;
}

数组开小了，应该是500010

by JSJ_WuYeHao @ 2024-11-08 09:40:37

@gukecheng 我去太牛了大佬,谢谢你,谢谢你,谢谢你!!!!!