Cheney_Z @ 2021-02-01 11:21:05
#include<bits/stdc++.h>
#define int long long
#define Please return
#define AC 0
using namespace std;
const int size = 5e5+10;
inline int read(){
int x = 0 , f = 1; char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') f = -1;
ch = getchar();
}
while(isdigit(ch)){
x = (x<<1) + (x<<3) + ch - 48;
ch = getchar();
}
return x * f;
}
int n,cnt;
int a[size],b[size];
void work(int l,int mid,int r){
memset(b,0,sizeof(b));
int i = l , j = mid+1;
for(int k=l;k<=r;++k){
if(i>mid) b[k] = a[j++], cnt += mid-i+1;
else if(j>r) b[k] = a[i++];
else if(a[i] <= a[j]) b[k] = a[i++];
else b[k] = a[j++],cnt += mid - i + 1;
}
for(int k=l;k<=r;++k) a[k] = b[k];
return;
}
void mysort(int l,int r){
if(l == r) return;
int mid = (l+r) >> 1;
mysort(l,mid);
mysort(mid+1,r);
work(l,mid,r);
return;
}
signed main(){
n = read();
cnt = 0;
for(int i=1;i<=n;++i) a[i] = read();
mysort(1,n);
printf("%lld\n",cnt);
Please AC;
}
by Cheney_Z @ 2021-02-01 11:21:39
是归并有问题吗
by Terrible @ 2021-02-01 11:31:07
memset(b,0,sizeof(b));
重复清空多次,复杂度接近
实际上不需要保证数组是空的,只要覆盖掉原来数据就好了,也调不出来原来的数据吧。
by 林聪 @ 2021-02-01 11:57:53
@Terrible 估计复杂度接近O(n^2log n)了
by Terrible @ 2021-02-01 12:08:54
一个16长的数组归并:
[1,16]
[1,8][9,16]
[1,4][5,8][9,12][13,16]
[1,2][3,4][5,6][7,8][9,10][11,12][13,14][15,16]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
排除l==r的情况,work调用次数为:
当n充分大的时候调用次数约是n次
by Terrible @ 2021-02-01 12:12:50
当
@林聪
by 林聪 @ 2021-02-01 15:30:00
@Terrible 哦确实,我直接用归并复杂度×n了
by Cheney_Z @ 2021-02-01 17:14:58
@Terrible @林聪 去掉memset就AC了 跪谢二位dalao