止步25

acmwriter @ 2024-01-23 20:24:49

#include<bits/stdc++.h>
using namespace std;
int a[500005],n;
long long ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(a[j]<a[i])ans++;
    cout<<ans;
    return 0;
}

by return_TLE @ 2024-01-23 20:29:59

@acmwriter 要用算法的

by ZjfAKIOI @ 2024-01-23 20:30:40

你用的是冒泡，n^2=2.5*1e11,肯定会超时。本题可以使用分治的思想来做，可以参考题解。

#include<bits/stdc++.h>
using namespace std;
int n,a[500005],c[500005];
long long ans;
void msort(int b,int e){
    if(b==e) return;
    int mid=(b+e)/2,i=b,j=mid+1,k=b;
    msort(b,mid),msort(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(){
    scanf("%d",&n); 
    for(int i=1;i<=n;i++) cin>>a[i];
    msort(1,n);
    cout<<ans;
    return 0;
}

by __My0217__ @ 2024-01-23 21:00:58

你可以使用权值线段树