为啥后十个点WA了

P1908 逆序对

Ricken @ 2019-08-15 22:36:16

#include<iostream>
using namespace std;
int a[1000001];
int r[1000001];//辅助数组 
int ans=0;
void msort(int s,int t){//归并排序
    if(s==t){
        return;//如果只有一个数字则返回 
    }
    int mid=(s+t)/2;
    msort(s,mid);//分解左序列 
    msort(mid+1,t); //分解右序列 
    int i=s,j=mid+1,k=s;//接下来合并 
    while(i<=mid&&j<=t){
        if(a[i]<=a[j]){
            r[k]=a[i];
            k++;
            i++;
        }
        else{
            r[k]=a[j];
            k++;
            j++;
            ans+=mid-i+1;
        }
    }
    while(i<=mid){//复制左边子序列剩余 
        r[k]=a[i];
        k++;
        i++;
    }
    while(j<=t){//复制右边子序列剩余 
        r[k]=a[j];
        k++;
        j++;
    }
    for(int i=s;i<=t;i++){
        a[i]=r[i];
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    msort(1,n);
    cout<<ans;
} 

by XeCtera @ 2019-08-15 22:40:27

@Ricken 答案要开long long存


by 由比滨丶雪乃 @ 2019-08-15 22:42:07

ans 要开 longlong

归并没问题


by Ricken @ 2019-08-16 09:28:53

哦,我知道了,谢谢@bcr_233 @由比滨丶雪乃 。


by 香格里拉太子 @ 2019-08-23 16:59:23

在你这里学到了归并排序,哈哈


|