求助

iTwinkle @ 2020-02-17 09:42:07

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN=1e5+10;
int a[MAXN],temp[MAXN];
LL ans=0;
void merge(int l,int r)
{
    if(l>=r)    return;
    int mid=(l+r)/2;
    merge(l,mid);
    merge(mid+1,r);

    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
    {
        if(a[i]>a[j])
        {
            temp[k]=a[i];
            k++;i++;ans+=mid-i+1;
        }
        else
        {
            temp[k]=a[j];
            k++;j++;
        }
    }
    while(i<=mid)
    {
        temp[k]=a[i];
        k++;i++;
    }
    while(j<=r)
    {
        temp[k]=a[j];
        k++;j++;
    }
    for(int i=l;i<=r;i++)   a[i]=temp[i];
    return;
}
int main()
{
    int n; scanf("%d",n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    merge(1,n);
    cout<<ans;
    return 0;
}

by liqingyang @ 2020-02-17 10:01:48

那也不会是死循环啊

by liqingyang @ 2020-02-17 10:01:57

应该是RE

by Krystallos @ 2020-02-17 10:03:02

归并他写错了

by liqingyang @ 2020-02-17 10:03:23

哪里？

by Krystallos @ 2020-02-17 10:04:54

把

while(i<=mid&&j<=r)
{
    if(a[i]>a[j])
    {
        temp[k]=a[i];
        k++;i++;ans+=mid-i+1;
    }
    else
    {
        temp[k]=a[j];
        k++;j++;
    }
}

换成

while(i<=mid&&j<=r)
{
    if(a[i]>a[j])
    {
        temp[k]=a[j];
        k++;j++;ans+=mid-i+1;
    }
    else
    {
        temp[k]=a[i];
        k++;i++;
    }
}

by liqingyang @ 2020-02-17 10:05:38

这样就不是死循环了

by liqingyang @ 2020-02-17 10:06:00

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN=1e5+10;
int a[MAXN],temp[MAXN];
LL ans=0;
void merge(int l,int r)
{
    if(l>=r)    return;
    int mid=(l+r)/2;
    merge(l,mid);
    merge(mid+1,r);

    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
    {
        if(a[i]>a[j])
        {
            temp[k]=a[i];
            k++;i++;ans+=mid-i+1;
        }
        else
        {
            temp[k]=a[j];
            k++;j++;
        }
    }
    while(i<=mid)
    {
        temp[k]=a[i];
        k++;i++;
    }
    while(j<=r)
    {
        temp[k]=a[j];
        k++;j++;
    }
    for(int i=l;i<=r;i++)   a[i]=temp[i];
    return;
}
int main()
{
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    merge(1,n);
    cout<<ans;
    return 0;
}

by liqingyang @ 2020-02-17 10:06:43

@iTwinkle 你再按照上面那位说的改一下应该就过了

by Krystallos @ 2020-02-17 10:06:50

@iTwinkle 错都找出来了

by liqingyang @ 2020-02-17 10:08:18

@iTwinkle 这样就过了

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN=1e5+10;
int a[MAXN],temp[MAXN];
LL ans=0;
void merge(int l,int r)
{
    if(l>=r)    return;
    int mid=(l+r)/2;
    merge(l,mid);
    merge(mid+1,r);

    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
    {
        if(a[i]>a[j])
        {
            temp[k]=a[j];
            k++;j++;ans+=mid-i+1;
        }
        else
        {
            temp[k]=a[i];
            k++;i++;
        }
    }
    while(i<=mid)
    {
        temp[k]=a[i];
        k++;i++;
    }
    while(j<=r)
    {
        temp[k]=a[j];
        k++;j++;
    }
    for(int i=l;i<=r;i++)   a[i]=temp[i];
    return;
}
int main()
{
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    merge(1,n);
    cout<<ans;
    return 0;
}