30pts球跳玄1关

imsbNR @ 2024-09-17 15:23:25

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 5;
ll n, a[N], c[N], cnt;
void merge(ll l, ll mid, ll r)
{
    ll i = l, j = mid + 1, k = 0;
    for (; i <= mid and j <= r;)
    {
        if (a[i] < a[j])
            c[++k] = a[i++];
        else
            c[++k] = a[j++], cnt += mid - i + 1;
    }
    while (i <= mid)
        c[++k] = a[i++];
    while (j <= r)
        c[++k] = a[j++];
    for (int i = l, j = 1; i <= r; i++, j++)
        a[i] = c[j];
    return;
}
void msort(ll l, ll r)
{
    if (l == r)
        return;
    ll mid = (l + r) >> 1;
    msort(l, mid);
    msort(mid + 1, r);
    merge(l, mid, r);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    msort(1, n);
    cout << cnt << '\n';
    return 0;
}

by furina_1013 @ 2024-09-17 16:30:42

@imsbNR

蒟蒻好懒，不想调 这是我的AC代码（删了头文件），可以看看思路

using namespace std;
#define int long long
int cnt =0;
void msort( int a[], int tmp[], int l, int r)
{
    if(l>=r) return;
    int mid=l+r>>1;
    msort(a, tmp, l, mid);
    msort(a, tmp, mid+1, r); 
    int i=l, j=mid+1, k=0;
    while(i<=mid && j<=r)
    {
        if(a[i]<=a[j])
        {
            tmp[k++]=a[i++];
        }
        else
        {
            cnt+= (mid-i+1);
            tmp[k++]=a[j++];
        }
    }

    while(i<=mid) tmp[k++]=a[i++];
    while(j<=r) tmp[k++]=a[j++];
    for(i=l, j=0;i<=r;i++, j++) a[i]=tmp[j];
}
#define MAXN 500010
int a[MAXN], tmp[MAXN];
signed main()
{
    int n; 
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    msort(a, tmp, 1, n);
    cout<<cnt<<endl;
}

by imsbNR @ 2024-09-17 16:32:00

@furina_1013 总不能是 <= 错了吧（捂脸笑）

by imsbNR @ 2024-09-17 16:33:05

@furina_1013 c，真是这

by furina_1013 @ 2024-09-18 20:22:31

@imsbNR

xixi对了就好