求调

Big_Big_Wolf @ 2023-08-22 20:54:36

#include<bits/stdc++.h>
using namespace std;
int n,a[1000000],b[100000],ans;
void s(int l,int r){
    if(r<=l) return;
    int m=(l+r)/2;
    s(l,m);s(m+1,r);
    int h1=l,h2=m+1,h=l;
    while(h1<=m&&h2<=r){
        if(a[h1]<a[h2])
            b[h++]=a[h1++];
        else b[h++]=a[h2++],ans+=m-h1+1; 
    }
    while(h1<m) b[h++]=a[h1++];
    while(h2<=r) b[h++]=a[h2++];
    for(int i=l;i<=r;i++) a[i]=b[i];
}//归并排序 
int main(){a
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    s(1,n);
    cout<<ans;
    return 0;
}

by tick_tock @ 2023-08-22 20:55:47

我来

by Big_Big_Wolf @ 2023-08-22 20:56:19

6

by Lionel__Messi @ 2023-08-22 20:57:14

@Big_Big_Wolf 我也来

by Big_Big_Wolf @ 2023-08-22 20:57:42

666

by guoxiaotong1234 @ 2023-08-22 20:59:04

#include<bits/stdc++.h>
using namespace std;
int n,a[1000000],b[1000000];
long long ans;
void s(int l,int r){
    int m=(l+r)/2;
    if(r==l) return;
    else{
        s(l,m);
        s(m+1,r);
    }
    int h1=l,h2=m+1,h=l;
    while(h1<=m&&h2<=r){

我们快下课了，只调了一点点QAQ

by tick_tock @ 2023-08-22 20:59:53

@Big_Big_Wolf

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
int n;
int a[N],b[N];
long long ans;
void fun(int l,int r)
{
    if(l==r)
    {
        return ;
    }   
    int mid=(l+r)/2,i=l,j=mid+1,k=l;
    fun(l,mid),fun(mid+1,r);
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[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;l<=r;l++)
    {
        a[l]=b[l];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    fun(1,n);
    cout<<ans;
    return 0;
}

让你借鉴一下

by Big_Big_Wolf @ 2023-08-22 21:00:06

ok谢谢

by Lionel__Messi @ 2023-08-22 21:01:04

@Big_Big_Wolf

#include <bits/stdc++.h>
using namespace std;
int n, a[500010], c[500010];
long long ans;
void dfs (int b, int e){
    if (b == e){
        return;
    } 
    int mid = (b + e) / 2, i = b, j = mid + 1, k = b;
    dfs (b, mid), dfs (mid + 1, e);
    while (i <= mid && j <= e){
        if (a[i] <= a[j]){
            c[k++] = a[i++];
        }else{
            c[k++] = a[j++], ans += mid - i + 1;
        }
    }
    while (i <= mid){
        c[k++] = a[i++];
    }   
    while (j <= e){
        c[k++] = a[j++];
    }   
    for (int l = b; l <= e; l++){
        a[l] = c[l];
    }
} 
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }   
    dfs(1, n);
    cout << ans;
    return 0;
}

我也让你借鉴一下