求助啊,怎么查都查不出问题。

P1908 逆序对

Kater_kcl @ 2019-07-25 23:39:24

#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
#include <cstdio>
#define ll long long
#define maxn 500005
using namespace std;
ll m[maxn];
int ans=0;
void mysort(ll l,ll r,ll mm[]){//左闭右开
    if (r-l<=1) {
        mm[0]=m[l];
        return;
    }
    ll mid=(l+r)/2;
    ll lt[mid-l+1],rt[r-mid+1];
    mysort(l, mid, lt);
    mysort(mid, r, rt);
    int pointl=0,pointr=0,i=0;
    while(pointl!=mid-l&&pointr!=r-mid){
        if(lt[pointl]<rt[pointr])
            mm[i++]=lt[pointl++];
        else{
            mm[i++]=rt[pointr++]; ans+=mid-pointl;}
    }
    if(pointl!=mid-l)
        while (i!=r-l) {mm[i++]=lt[pointl++];}
    else
        while (i!=r-l) {mm[i++]=rt[pointr++];}
}
int main(){
    int n;
    cin>>n;
    for (int i=0; i<n; i++) {
        scanf("%lld", &m[i]);
    }
    mysort(0, n, m);
    cout<<ans;
    return 0;
}

by 万弘 @ 2019-07-26 07:52:49

@Kater_kcl ll lt[mid-l+1],rt[r-mid+1];是什么操作


by Kater_kcl @ 2019-07-26 09:12:28

@万弘 左右辅助数组啊(萌新不会只定义一个数组)


by 万弘 @ 2019-07-26 09:36:32

@Kater_kcl 你是RE还是WA


by Kater_kcl @ 2019-07-26 09:36:51

@万弘 wa


by 万弘 @ 2019-07-26 09:39:54

mysort(l, mid, lt);
mysort(mid, r, rt);

应该改成

mysort(l, mid, lt);
mysort(mid+1, r, rt);

by Kater_kcl @ 2019-07-28 13:32:11

@万弘 谢谢谢谢


by Kater_kcl @ 2019-07-28 13:35:31

@万弘 但是改了之后依然不对啊QAQ


|