Ultra-QuickSort Time Limit:7000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu Submit
Status 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 9 1 0 5 4 3 1 2 3 0 Sample Output 6 0 题意：给你 n 个数让，每次只能交换相邻的两个数，问多少次后他们能从小到大排序
这里第一个是归并排序，看一位大神的博客，挺好的点此进入 大致意思就是把一个区间二分二分再二分，知道最小的只有两个数的时候比较一下，统计移动次数，然后递归合并合并再合并，再统计，里面最主要的意思就是，在移动一个数位置时，移动的距离等于变换的次数，记录就好了
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define LL long long #define M 500050 LL temp[M], ans, num[M]; void merge(int low, int mid, int high) { int i = low, j = mid+1, k = low;//依旧是二分的思想 while(i <= mid && j <= high)//左右进行比较 { if(num[i] <= num[j])//前面的比后面的小就直接记录 { temp[k++] = num[i++];//temp是临时记录一下排序的结果位置 } else//反之就移动过去在记录次数，再记录位置 { ans += (j - k); temp[k++] = num[j++]; } } while(i <= mid) temp[k++] = num[i++];//未完待续。。。 while(j <= high) temp[k++] = num[j++]; for(i=low; i<=high; i++)//回归 { num[i] = temp[i]; } } void meger_sort(int a, int b)//交换的区间 { if(a < b) { int mid = (a + b) >> 1; meger_sort(a, mid);//进入左区间 meger_sort(mid+1, b);//进去右区间 merge(a, mid, b);//先排列每一个小区间里面的，然后再排大区间 } } int main() { int n; while(scanf("%d", &n) && n) { for(int i=0; i<n; i++) { scanf("%lld", &num[i]); } ans = 0; meger_sort(0, n-1); printf("%lld\n", ans); } return 0; }下面是树状数组来求的，还是推荐大神博客[链接在此]http://www.cnblogs.com/shenshuyang/archive/2012/07/14/2591859.html
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define LL long long #define M 500010 struct node { int val, order; }; node no[M]; bool cmp(node a, node b) { return a.val < b.val; } int tree[M], reflect[M], n; int lowbit(int x) { return x & (-x); } void updata(int x) { while(x <= n) { tree[x]++; x += lowbit(x); } } int sumtree(int x) { int sum = 0; while(x > 0) { sum += tree[x]; x -= lowbit(x); } return sum; } int main() { while(scanf("%d", &n) && n) { for(int i=1; i<=n; i++) { scanf("%d", &no[i].val); no[i].order = i; } sort(no+1, no+1+n, cmp); for(int i=1; i<=n; i++) tree[i] = 0; for(int i=1; i<=n; i++) { reflect[no[i].order] = i;//离散化，位置没变，但是数变小了，以后用reflect[i]就可以表示原来的位置为 i,当前的位置就是reflect[i] } LL ans = 0; for(int i=1; i<=n; i++)// i 表示当前插入树状数组的个数 { updata(reflect[i]);//将 reflect[i]插入 //倘若按顺序排的话，插入reflect[i]的时候，sumtree[reflect[i]]的值与 i 是一样的，如果不一样就说明有比reflect[i]更大的数已经先插入了树里面，用 i 减去 sumtree[reflect[i]],就可以得到有多少个比 reflect[i] 小的数排在前面 ans += i - sumtree(reflect[i]);//sumtree( reflect[i] ）为比 reflect[i] 小的数的个数 //i - sumtree(reflect[i])就求出来逆序对数（ a > b 就是一个逆序对数，顺序与所求顺序相逆） } printf("%lld\n", ans); } return 0; }下面是自己琢磨出来的线段树，大致上和树状数组的思想一样啦
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define LL long long #define lson l, mid, rt<<1 #define rson mid+1, r, rt<<1|1 #define M 500010 int n; struct node { int val, order; }; node no[M]; int tree[M<<2], reflect[M]; void pushup(int rt) { tree[rt] = tree[rt<<1] + tree[rt<<1|1]; } void updata(int p, int add, int l, int r, int rt) { if(r == l) { tree[rt] += add; return ; } int mid = (l + r) >> 1; if(p <= mid) { updata(p, add, lson); } else { updata(p, add, rson); } pushup(rt); } int query(int le, int re, int l, int r, int rt) { int sum = 0; if(le <= l && re >= r) { return tree[rt]; } int mid = (r + l) >> 1; if(le <= mid) { sum += query(le, re, lson); } if(re > mid) { sum += query(le, re, rson); } return sum; } bool cmp(node a, node b) { return a.val < b.val; } int main() { while(scanf("%d", &n) != EOF && n) { for(int i=1; i<=n; i++) { scanf("%d", &no[i].val); no[i].order = i; } sort(no+1, no+1+n, cmp); memset(tree, 0, sizeof(tree)); for(int i=1; i<=n; i++) { reflect[no[i].order] = i; } LL sum = 0; for(int i=1; i<=n; i++) { updata(reflect[i], 1, 1, n, 1); sum += i - query(1, reflect[i], 1, n, 1); } printf("%lld\n", sum); } return 0; }