C++归并排序30分 有AC有WA还有TLE

P1908 逆序对

a2lyaXNhbWUgbWFyaXNh @ 2022-07-22 11:43:03

求调，本蒟蒻找不出问题在哪QAQ，%%%膜拜大佬%%%

悬赏关注

注：吸氧后提升了10分

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[500010],b[500010],n,ans;
inline int read() {//快读
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x) {//快写
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10 +'0');
}
inline void mgs(int l,int r) {//归并+统计
    if(l==r)return;
    int mid=(l+r)/2;
    mgs(l,mid);
    mgs(mid+1,r);
    int p1=l,p2=mid+1,p3=l;
    while(p1<=mid&&p2<=r) {
        if(a[p1]<a[p2])b[p3++]=a[p1++];
        else{
            b[p3++]=a[p2++];
            ans+=mid-p1+1;
        } 
    }
    while(p1<=mid)b[p3++]=a[p1++];
    while(p2<=r)b[p3++]=a[p2++];
    for(int i=1; i<=r; i++)a[i]=b[i];
}
signed main() {//main包
    n=read();
    for(int i=1; i<=n; i++)a[i]=read();
    mgs(1,n);
    write(ans);
    return 0;//好习惯
}
//然而30分，O2YYDS

by Register_int @ 2022-07-22 11:47:07

@S__B if(a[p1]<a[p2])b[p3++]=a[p1++];->if(a[p1]<=a[p2])b[p3++]=a[p1++];

by a2lyaXNhbWUgbWFyaXNh @ 2022-07-22 11:49:21

@Register_int thx，我去试试

by a2lyaXNhbWUgbWFyaXNh @ 2022-07-22 11:49:35

话说能不能卡常啊

by Register_int @ 2022-07-22 11:49:59

@S__B for(int i=1; i<=r; i++)a[i]=b[i];->for(int i=l; i<=r; i++)a[i]=b[i];

by Trafford1894 @ 2022-07-22 11:50:40

for(int i=1; i<=r; i++)a[i]=b[i];

->

for(int i=l; i<=r; i++)a[i]=b[i];

by Trafford1894 @ 2022-07-22 11:50:54

@S__B

by Register_int @ 2022-07-22 11:51:07

@S__B AC记录。你这复杂度是小常数 O(n^2)，当然T

by Eason2009 @ 2022-07-22 11:51:18

@S__B 帮您改了一下，AC了

AC code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[500010],b[500010],n,ans;
inline int read() {//快读
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x) {//快写
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10 +'0');
}
inline void mgs(int l,int r) {//归并+统计
    if(l==r)return;
    int mid=(l+r)/2;
    mgs(l,mid);
    mgs(mid+1,r);
    int p1=l,p2=mid+1,p3=l;
    while(p1<=mid&&p2<=r) {
        if(a[p1]<=a[p2])b[p3++]=a[p1++];
        else{
            b[p3++]=a[p2++];
            ans+=mid-p1+1;
        } 
    }
    while(p1<=mid)b[p3++]=a[p1++];
    while(p2<=r)b[p3++]=a[p2++];
    for(int i=l; i<=r; i++)a[i]=b[i];
}
signed main() {//main包
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    mgs(1,n);
    cout<<ans;
    return 0;//好习惯
}
//然而30分，O2YYDS

by a2lyaXNhbWUgbWFyaXNh @ 2022-07-22 11:51:27

@Register_int 感谢大佬！50分了！剩下的只有TLE了！%%%

by Eason2009 @ 2022-07-22 11:51:46

改了merge函数中的两个地方

| 下一页