2012-10-17 18:08:55Morris
[ZJ][非遞迴合併排序] d542. 10810 - Ultra-QuickSort
內容 ：
在這個問題中你必須去分析一個特別的排序演算法 Ultra-QuickSort。這個演算法要將 n 個不同的整數由小到大排序，所用的動作是在必要的時候將 相鄰 的 2 個數交換。對以下的輸入序列： 9 1 0 5 4 這個 Ultra-QuickSort 將會產生以下的輸出： 0 1 4 5 9 你的任務是算出 Ultra-QuickSort 最少需要用到多少次交換的動作，來將輸入的序列由小到大排序。 |
輸入說明
：
輸入含有多組測試資料。
每組測試資料的第一列
有 1 個整數 n（ n < 500000）
代表需要排序的整數有多少個
接下來的 n 列每列有一個整數 (0 <= a[i] <= 999999999)
代表要排序的數
當 n=0 時代表輸入結束
請參考 Sample Input
輸出說明
：
對每一組測試資料輸出一列
最少需要用到多少次交換的動作
來將輸入的序列由小到大排序
範例輸入
：
5 9 1 0 5 4 3 1 2 3 4 4 3 2 1 0
範例輸出 ：
6 0 6
提示
：
* 中文翻譯 : Lucky貓
* 測資有誤請通知
出處
：
Uva 10810
(管理：morris1028)
.
#include <stdio.h>
int A[500000], X[500000];
long long merge(int l, int m, int r) {
int idx1 = l, idx2 = m+1, top = 0;
int i, j;
long long cnt = 0, subans = 0;
while(idx1 <= m && idx2 <= r) {
if(A[idx1] <= A[idx2])
X[top++] = A[idx1++], subans += cnt;
else
X[top++] = A[idx2++], cnt++;
}
while(idx1 <= m) X[top++] = A[idx1++], subans += cnt;
while(idx2 <= r) X[top++] = A[idx2++];
for(i = 0, j = l; i < top; i++, j++)
A[j] = X[i];
return subans;
}
void solve(int *A, int n) {
int i, j;
long long ans = 0;
for(i = 1; i < n; i <<= 1) {
for(j = 0; j < n; j += i) {
if(j+i-1 < n)
ans += merge(j, j+i/2-1, j+i-1);
else
ans += merge(j, j+i/2-1, n-1);
}
}
ans += merge(0, i/2-1, n-1);
printf("%lld\n", ans);
}
int main() {
int n, i;
while(scanf("%d", &n), n) {
for(i = 0; i < n; i++)
scanf("%d", &A[i]);
solve(A, n);
}
return 0;
}
.
#include <stdio.h>
int A[500000], X[500000];
long long merge(int l, int m, int r) {
int idx1 = l, idx2 = m+1, top = 0;
int i, j;
long long cnt = 0, subans = 0;
while(idx1 <= m && idx2 <= r) {
if(A[idx1] <= A[idx2])
X[top++] = A[idx1++], subans += cnt;
else
X[top++] = A[idx2++], cnt++;
}
while(idx1 <= m) X[top++] = A[idx1++], subans += cnt;
while(idx2 <= r) X[top++] = A[idx2++];
for(i = 0, j = l; i < top; i++, j++)
A[j] = X[i];
return subans;
}
void solve(int *A, int n) {
int i, j;
long long ans = 0;
for(i = 1; i < n; i <<= 1) {
for(j = 0; j < n; j += i) {
if(j+i-1 < n)
ans += merge(j, j+i/2-1, j+i-1);
else
ans += merge(j, j+i/2-1, n-1);
}
}
ans += merge(0, i/2-1, n-1);
printf("%lld\n", ans);
}
int main() {
int n, i;
while(scanf("%d", &n), n) {
for(i = 0; i < n; i++)
scanf("%d", &A[i]);
solve(A, n);
}
return 0;
}
此 code 有問題，待修正