首页 > 代码库 > poj2299--归并排序求逆序数
poj2299--归并排序求逆序数
/** \brief poj2299 * * \param date 2014/8/5 * \param state AC * \return memory 4640K time 3250ms * */ #include <iostream> #include <fstream> #include <cstdio> #include <cstring> using namespace std; const int MAXN=500000; int Arr[MAXN]; int T[MAXN]; //__int64 t; __int64 t; void merge_sort(int* A,int x,int y,int* T) { if(y-x>1) { int m=x+(y-x)/2;//partition int p=x,q=m,i=x; merge_sort(A,x,m,T); merge_sort(A,m,y,T); while(p<m || q<y) { if(q>=y || (p<m && A[p]<=A[q])) T[i++]=A[p++];//从左半数组复制到临时空间 else { T[i++]=A[q++];//从右半数组…… t+=m-p;//统计逆序数对 } } for(int i=x;i<y;i++) A[i]=T[i];//从辅助空间复制回A数组 } } int main() { //cout << "Hello world!" << endl; //freopen("input.txt","r",stdin); int n=0; while(scanf("%d",&n)) { if(n==0)break; memset(Arr,0,sizeof(Arr)); memset(T,0,sizeof(T)); for(int i=0;i<n;i++) cin>>Arr[i]; merge_sort(Arr,0,n,T); printf("%I64d",t); t=0; cout<<endl; } return 0; }
用归并排序求序列的逆序数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。