首页 > 代码库 > zoj 2386 - Ultra-QuickSort
zoj 2386 - Ultra-QuickSort
题目:只允许交换相邻元素的排序,统计将最小交换次数。
分析:分治,逆序数。在合并排序的过程中进行逆序对的求解。
合并A,B两个字串时利用两根指针作为计数;
当B中元素放入新数组时A中所剩元素一定大于B;
每次计数加和即可。
说明:置换群 可以用来计算任意最小交换。。。 (2011-09-20 14:25)
#include <stdio.h> #include <stdlib.h> int Data[ 500005 ]; int Save[ 500005 ]; long long MergeSort( int a, int b ) { if ( a < b ) { long long L = MergeSort( a, (a+b)/2 ); long long R = MergeSort( (a+b)/2+1, b ); //Merge long long Count = L+R; int ps = a,pe = (a+b)/2; int qs = (a+b)/2+1,qe = b; int move = a; while ( ps <= pe || qs <= qe ) if ( qs <= qe && ( ps == pe+1 || Data[ ps ] > Data[ qs ] ) ) { Save[ move ++ ] = Data[ qs ++ ]; Count += pe-ps+1LL;//计算A B 中的逆序数 }else Save[ move ++ ] = Data[ ps ++ ]; for ( int i = a ; i <= b ; ++ i ) Data[ i ] = Save[ i ]; return Count; }else return 0LL; } int main() { int n; while ( scanf("%d",&n) && n ) { for ( int i = 1 ; i <= n ; ++ i ) scanf("%d",&Data[ i ]); printf("%lld\n",MergeSort( 1, n )); } return 0; }
zoj 2386 - Ultra-QuickSort
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。