[ZJ][非遞迴合併排序] d542. 10810 - Ultra-QuickSort＠Morris' Blog

2012-10-17 18:08:55| 人氣3,706| 回應1 | 上一篇 | 下一篇

[ZJ][非遞迴合併排序] d542. 10810 - Ultra-QuickSort

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

在這個問題中你必須去分析一個特別的排序演算法 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

輸出說明：

對每一組測試資料輸出一列

最少需要用到多少次交換的動作

來將輸入的序列由小到大排序

範例輸入： help

範例輸出：

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;
}

我要檢舉

#非遞迴合併排序#merge#sort

台長： Morris

您可能對以下文章有興趣

a181. 逆逆向思考

[ZJ][D&C] d847 2D rank finding problem

d633. 幼稚王國的麥田圖騰

d828. Pascal's triangle's secret (II)

人氣(3,706) | 回應(1)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][塊狀表] d476. 区间查询
此分類上一篇:[ZJ][插頭DP] a228. 就少一個插座用很不方便

回應(1)