[TOJ] 11- bubble, WA 求解，使用 Merge Sort

amoshuangyc

http://toj.twbbs.org/oj/chal/1863/

使用 Merge Sort （遞迴）可能會 TLE 沒錯，但我第一筆測資就 WA，可是我找不到程式哪裡錯了。

#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[i];

        

        long long cnt = merge_sort(0, N-1);

        

        cout << cnt << endl;

        

        return 0;

}