C++逆序对数目的求解

题目来源(洛谷P1908 逆序对)

题目链接：

求逆序对的数目https://www.luogu.com.cn/problem/P1908

逆序对数目的求解方法，一种是基于冒泡排序，另一种是基于归并排序。

基于冒泡排序的算法：(O(n^2))

#include
int num[500001];
int tot;
unsigned long long sum=0;
inline int read(){int res=0;char c=getchar();while(c>='0' && c<='9'){res=(res<<1)+(res<<3)+(c^48); c=getchar();} return res;
}
inline void write(unsigned long long num){if(num!=0){write(num/10);putchar((num%10)^48);}
}
int main(){bool check;tot=read();for(int i=1;i<=tot;i++){num[i]=read();}for(int i=1;i<=tot;i++){check=false;for(int j=1;j<=tot-i;j++){if(num[j]>num[j+1]){check=true;int temp=num[j];num[j]=num[j+1];num[j+1]=temp;sum++;}}if(!check)break;}write(sum);return 0;
} 

基于归并排序的算法：(O(nlogn))

#include
int tot;
unsigned long long sum=0;
int num[500001];
int ans[500001];
inline int read(){int res=0;char c=getchar();while(c>='0' && c<='9'){res=(res<<1)+(res<<3)+(c^48); c=getchar();} return res;
}
inline void write(unsigned long long num){if(num!=0){write(num/10);putchar((num%10)^48);}
}
void msort(int l,int r){if(l==r)return;int mid=(l+r)/2;msort(l,mid);msort(mid+1,r);int a=l,b=mid+1;int k=l; while(a<=mid && b<=r){if(num[a]<=num[b]){ans[k]=num[a];a++;k++;}else{ans[k]=num[b];b++;k++;sum+=mid-a+1;}}while(a<=mid){ans[k]=num[a];a++;k++;}while(b<=r){ans[k]=num[b];b++;k++;}for(int i=l;i<=r;i++){num[i]=ans[i];}
}
int main(){tot=read();for(int i=1;i<=tot;i++){num[i]=read();}msort(1,tot);write(sum);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！