TOJ 11 bubble

allenwhale

題目很簡單，問bubble sort 一個序列需要交幾次
有一個重點是bubble sort，如果用了其他種sort答案就會不一樣

做法1:就直接做一次bubble sort就好，當然會TLE

做法2:merge sort
很剛好的，做merge sort時，一邊計算交換次數就剛好是bubble sort的交換次數~

做法3:樹狀數組(附AC code)
這是一種很神奇的資料結構，可以把它想像成瘦身後的線段樹
資料參考:
http://hawstein.com/posts/binary-indexed-trees.html
http://zh.wikipedia.org/wiki/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84
如此如此這般這般地做完就AC了~~
AC code

[C++] 純文本查看 復制代碼

#include <stdio.h>
#include <string.h>
typedef long long ll;
int bit[20000010];
int N;
int sum(int x)
{
    int s=0;
    while(x>0)
    {
        s+=bit[x];
        x-=x&(-x);
    }
    return s;
}
void add(int x,int d)
{
    while(x<=N)
    {
        bit[x]+=d;
        x+=x&(-x);
    }
}
int main()
{
    memset(bit,0,sizeof(bit));
    scanf("%d",&N);
    ll ans=0;
    for(int i=0;i<N;i++)
    {
        int index;
        scanf("%d",&index);
        ans+=(ll)i-(ll)sum(index);
        add(index,1);
    }
    printf("%lld\n",ans);
    return 0;
}

amoshuangyc

這裡給出 merge sort 的解法。

考慮 merge 的過程：
左邊陣列中要比較的值為 A
右邊陣列中要比較的值為 B
當 B < A 時，必需將 B 左移到 A 之前，這時 B 左移時所越過的所有值都比 B 大。也就是說，B 與它所越過的值形成逆序數對，也就是題目要求的東西。
左移的過程就是 B 從右至左依序交換那些數。
越過的值的個數 就是 逆序數對數。

以下圖舉例：


6 得與 12, 11, 7 交換。注意，此時 1, 3, 2 已經排好了，也就是說 1, 3, 2 已經不在待比較的陣列中，已經被移到 結果陣列中了，所以我們不須考慮這三個數。
逆序數對：(12, 6), (11, 6), (7, 6)。

從上圖可以得知，得與 (m - idx_L + 1) 個 數交換。

完整 code ：

[C++] 純文本查看 復制代碼

#include <iostream>

using namespace std;

int data[2000000+1];
int temp[2000000+1];

long long merge(int p, int m, int q)
{
    int idx_L = p;
    int idx_R = m + 1;
    int idx_temp = p;
    
    long long cnt = 0;
    
    while (idx_L <= m && idx_R <= q) {
        if (data[idx_L] <= data[idx_R]) {
            temp[idx_temp++] = data[idx_L++];
        }
        else {
            temp[idx_temp++] = data[idx_R++];
            cnt += (m - idx_L + 1); // 記算逆序數對數
        }
    }
    
    while (idx_L <= m)
        temp[idx_temp++] = data[idx_L++];
    while (idx_R <= q)
        temp[idx_temp++] = data[idx_R++];
        
    for (int i=p; i<=q; i++)
        data[i] = temp[i];
    
    return cnt;
}

long long merge_sort(const int p, const int q)
{
    if (p >= q) return 0;
    
    int m = (p+q) / 2;
    long long cnt_L = merge_sort(p, m);
    long long cnt_R = merge_sort(m+1, q);
    long long cnt_M = merge(p, m, q);
    
    return (cnt_L + cnt_R + cnt_M);
}

int main()
{
    int N;
    cin >> N;
    
    for (int i=0; i<N; i++)
        cin >> data;
    
    long long cnt = merge_sort(0, N-1);
    
    cout << cnt << endl;
    
    return 0;
}