首页 > 代码库 > NUC_TeamTEST_C && POJ2299（只有归并）
NUC_TeamTEST_C && POJ2299（只有归并）
Ultra-QuickSort
Description  In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence Ultra-QuickSort produces the output Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence. Input The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed. Output For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence. Sample Input 59105431230 Sample Output 60 Source Waterloo local 2005.02.05 |
这道题就是通过求逆序数的和，来求出序列所有的交换次数。用冒泡排序直接会TLE（相当于暴力了），
这道题有3种解法，树状数组、线段树、归并排序（O（N*lgN））
其中归并排序的写法应该是最简单的，树状数组、线段树要用到离散化，博客后续还会跟上
归并写法，其实归并写法，自己并不是很熟练，推介大牛博客
http://blog.163.com/zhaohai_1988/blog/static/20951008520127321239701/
大牛代码真心漂亮!!中间核心，就是学大牛写的
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #define LL long long //LL 代替 long long 的写法 中间数据会超出 int
5 using namespace std; 6 7 const int max_size = 500010; 8 9 int arry[max_size], tmp_arry[max_size];10 11 LL Merge(int *arr, LL beg, LL mid, LL end, int *tmp_arr)12 {13 memcpy(tmp_arr+beg, arr+beg, sizeof(int)*(end-beg+1));14 LL i = beg;15 LL j = mid + 1;16 LL k = beg;17 LL inversion = 0;18 while(i <= mid && j <= end)19 {20 if(tmp_arr[i] <= tmp_arr[j]) ///如果合并逆序数的时候，前边小于等于后边，就不用记录逆序数的值21 {22 arr[k++] = tmp_arr[i++];23 }else{24 arr[k++] = tmp_arr[j++]; ///如果不是，则要记录逆序数的值25 inversion += (mid - i + 1);///简单画下就能看出26 }27 }28 29 while(i <= mid) ///把没有并入arr数组的数并入30 31 {32 arr[k++] = tmp_arr[i++];33 }34 while(j <= end)35 {36 arr[k++] = tmp_arr[j++];37 }38 return inversion;39 }40 41 LL MergeInversion(int *arr, LL beg, LL end, int *tmp_arr)42 {43 LL inversions = 0;44 if(beg < end)45 {46 LL mid = (beg + end) >> 1;47 inversions += MergeInversion(arr, beg, mid, tmp_arr); ///分成两段分别进行记录，递归的进行下去，找逆序数和48 inversions += MergeInversion(arr, mid+1, end, tmp_arr);49 inversions += Merge(arr, beg, mid, end, tmp_arr);50 }51 return inversions;52 }53 54 int main()55 {56 LL n;57 58 while(cin >> n)59 {60 if(n == 0)61 break;62 for(int i = 0; i < n; ++i)63 scanf("%d", &arry[i]);64 memcpy(tmp_arry, arry, sizeof(int)*n);65 cout << MergeInversion(arry, 0, n-1, tmp_arry) << endl;66 }67 return 0;68 }
NUC_TeamTEST_C && POJ2299（只有归并）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。