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
9 1 0 5 4 , Ultra-QuickSort produces the output 0 1 4 5 9 . 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 5 Sample Output 6 Source |
这道题就是通过求逆序数的和,来求出序列所有的交换次数。用冒泡排序直接会TLE(相当于暴力了),
这道题有3种解法,树状数组、线段树、归并排序(O(N*lgN))
其中归并排序的写法应该是最简单的,树状数组、线段树要用到离散化,博客后续还会跟上
归并写法,其实归并写法,自己并不是很熟练,推介大牛博客
http://blog.163.com/zhaohai_1988/blog/static/20951008520127321239701/
大牛代码真心漂亮!!中间核心,就是学大牛写的
#include <cstdio>
#include <iostream>
#include <cstring>
#define LL long long //LL 代替 long long 的写法 中间数据会超出 int
using namespace std; const int max_size = ; int arry[max_size], tmp_arry[max_size]; LL Merge(int *arr, LL beg, LL mid, LL end, int *tmp_arr)
{
memcpy(tmp_arr+beg, arr+beg, sizeof(int)*(end-beg+));
LL i = beg;
LL j = mid + ;
LL k = beg;
LL inversion = ;
while(i <= mid && j <= end)
{
if(tmp_arr[i] <= tmp_arr[j]) ///如果合并逆序数的时候,前边小于等于后边,就不用记录逆序数的值
{
arr[k++] = tmp_arr[i++];
}else{
arr[k++] = tmp_arr[j++]; ///如果不是,则要记录逆序数的值
inversion += (mid - i + );///简单画下就能看出
}
} while(i <= mid) ///把没有并入arr数组的数并入 {
arr[k++] = tmp_arr[i++];
}
while(j <= end)
{
arr[k++] = tmp_arr[j++];
}
return inversion;
} LL MergeInversion(int *arr, LL beg, LL end, int *tmp_arr)
{
LL inversions = ;
if(beg < end)
{
LL mid = (beg + end) >> ;
inversions += MergeInversion(arr, beg, mid, tmp_arr); ///分成两段分别进行记录,递归的进行下去,找逆序数和
inversions += MergeInversion(arr, mid+, end, tmp_arr);
inversions += Merge(arr, beg, mid, end, tmp_arr);
}
return inversions;
} int main()
{
LL n; while(cin >> n)
{
if(n == )
break;
for(int i = ; i < n; ++i)
scanf("%d", &arry[i]);
memcpy(tmp_arry, arry, sizeof(int)*n);
cout << MergeInversion(arry, , n-, tmp_arry) << endl;
}
return ;
}