全WA求调，悬关

zhyn @ 2024-10-22 18:18:30

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 500005

ll n,num[maxn],t[maxn];

ll ans=0;

void meg(int l,int r){
    if(l==r){
        return;
    }
    int mid=(l+r)/2;
    meg(l,mid),meg(mid+1,r);
    for(int i=l,j=mid+1,k=l;k<=r;k++){
        if(i==mid+1){
            t[k]=num[j++];
        }
        if(j==r+1){
            t[k]=num[i++];
        }
        else{
            if(num[i]<=num[j]){
                t[k]=num[i++];
            }
            else{
                t[k]=num[j++];
                ans+=mid-i+1;
            }
        }
    }
    for(int i=l;i<=r;i++){
        num[i]=t[i];
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>num[i];
    }

    meg(1,n);

    cout<<ans;

    return 0;
} 

by Goodans @ 2024-10-22 18:48:37

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

ll merge_and_count(vector<ll>& num, vector<ll>& temp, int left, int mid, int right) {
    int i = left; 
    int j = mid + 1; 
    int k = left; 
    ll inv_count = 0;

    while ((i <= mid) && (j <= right)) {
        if (num[i] <= num[j]) {
            temp[k++] = num[i++];
        } else {
            temp[k++] = num[j++];
            inv_count += (mid - i + 1); 
        }
    }

    while (i <= mid) {
        temp[k++] = num[i++];
    }

    while (j <= right) {
        temp[k++] = num[j++];
    }

    for (i = left; i <= right; i++) {
        num[i] = temp[i];
    }

    return inv_count;
}

ll merge_sort_and_count(vector<ll>& num, vector<ll>& temp, int left, int right) {
    ll inv_count = 0;
    if (left < right) {
        int mid = (left + right) / 2;

        inv_count += merge_sort_and_count(num, temp, left, mid);
        inv_count += merge_sort_and_count(num, temp, mid + 1, right);
        inv_count += merge_and_count(num, temp, left, mid, right);
    }
    return inv_count;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    ll n;
    cin >> n;
    vector<ll> num(n + 1), temp(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> num[i];
    }

    ll ans = merge_sort_and_count(num, temp, 1, n);
    cout << ans << "\n";

    return 0;
}

改了vector，函数分离，AC了。

by Goodans @ 2024-10-22 18:49:06

@zhyn 已改，求关

by zhyn @ 2024-10-22 19:00:01

可以解释一下为什么我的错了么

by zhyn @ 2024-10-25 20:18:04

此贴结