石油湖（TLE)

guer_loser_lcz @ 2023-11-26 16:43:01

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int a[501000],b[501000],c[501000];
long long ans,n;
void gbpx(int x,int y){
    int mid=(x+y)/2;
    if(x==y)return;
    else{
        gbpx(x,mid);
        gbpx(mid+1,y);
    }
    int i=x;
    int j=mid+1;
    int k=x;
    while(i<=mid&&j<=y){
        if(a[i]<=b[j]){
            b[k]=a[i];
            i++;
        }
        if(a[i]>a[j]){
            b[k]=a[j];
            j++;
            ans+=(mid-i+1);
        }
        k++;
    }
    while(i<=mid){
    b[k]=a[i];
    k++,i++;
    }
    while(j<=y){
    b[k]=a[j];
    k++,j++;
    }
    for(int i=x;i<=y;i++){
        a[i]=b[i];
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    gbpx(1,n);
    cout<<ans;
    return 0;
}

by sdyzpf @ 2023-11-26 17:30:09

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int a[501000],b[501000],c[501000];
long long ans,n;
void gbpx(int x,int y){
    int mid=(x+y)/2;
    if(x==y)return;
    else{
        gbpx(x,mid);
        gbpx(mid+1,y);
    }
    int i=x;
    int j=mid+1;
    int k=x;
    while(i<=mid&&j<=y){
        if(a[i]<=a[j]){
            b[k]=a[i];
            i++;
        }
        else{
            b[k]=a[j];
            j++;
            ans+=(mid-i+1);
        }
        k++;
    }
    while(i<=mid){
    b[k]=a[i];
    k++,i++;
    }
    while(j<=y){
    b[k]=a[j];
    k++,j++;
    }
    for(int i=x;i<=y;i++){
        a[i]=b[i];
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    gbpx(1,n);
    cout<<ans;
    return 0;
}

by Mr_RedStone @ 2023-11-28 20:21:36

@lczcy1

改完的

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int a[501000],b[501000],c[501000];
long long ans,n;
void gbpx(int x,int y){
  int mid=(x+y)/2;
  if(x==y)return;
  else{
    gbpx(x,mid);
    gbpx(mid+1,y);
  }
  int i=x;
  int j=mid+1;
  int k=x;
  while(i<=mid&&j<=y){
    if(a[i]>a[j]){
      b[k]=a[j];
      j++;
      ans+=(mid-i+1);
    }
    else{
      b[k]=a[i];
      i++;
    }
    k++;
  }
  while(i<=mid){
    b[k]=a[i];
    k++,i++;
  }
  while(j<=y){
    b[k]=a[j];
    k++,j++;
  }
  for(int i=x;i<=y;i++){
    a[i]=b[i];
  }
}
int main(){
  cin>>n;
  for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
  }
  gbpx(1,n);
  cout<<ans;
  return 0;
}

俩问题

第一个是

if(a[i]<=b[j]){
  b[k]=a[i];
  i++;
}

是a[i]<=a[j] ......

第二个(亿点点严重)

if(a[i]<=b[j]){
  b[k]=a[i];
  i++;
}
if(a[i]>a[j]){
  b[k]=a[j];
  j++;
  ans+=(mid-i+1);
}

这两个应该写成

if(a[i]>a[j]){
  b[k]=a[j];
  j++;
  ans+=(mid-i+1);
}
else{
  b[k]=a[i];
  i++;
}

因为如果不用else进行判断，那么上面第一个if执行了以后i++，然后下面的if又发现这个新的a[i]>a[j]就又多执行一次，会有问题

by guer_loser_lcz @ 2023-11-28 20:56:47

@Mr_RedStone 感谢老二！！

日常脑can

恍然大悟！！