___wa___ @ 2023-04-11 20:10:14
rt,用裸的归并排序改了改,WA了后10个点
#include<bits/stdc++.h>
using namespace std;
int a[5000005];
int ans=0;
void msort(int s,int t)
{
int r[5000005];
if(s==t) return;
int m=(s+t)/2;
msort(s,m);
msort(m+1,t);
int i=s,j=m+1,k=s;
while(i<=m&&j<=t)
{
if(a[i]<=a[j])
{
r[k]=a[i];
k++; i++;
}
else
{
r[k]=a[j];
k++; j++;
ans+=m-i+1;
}
}
while(i<=m)
{
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];
return ;
}
int main()
{
int b;
scanf("%d",&b);
for(int i=1;i<=b;i++)
scanf("%d",&a[i]);
msort(1,b);
printf("%d ",ans);
return 0;
}
数组肯定开的够大了吧...
by Ruiqun2009 @ 2023-04-11 20:22:17
@wa long long
.
by ___wa___ @ 2023-04-11 20:22:59
@Ruiqun2009 谢(