Lotplace

本人於該blog的全部文章轉移至[UVA] 11495 Bubbles and Buckets – KKWBlog (kkwtech.com)該網域下，其後此處不進行更新，一律於新站點更新。

d195. 11495 – Bubbles and Buckets – 高中生程式解題系統 (zerojudge.tw)
題目重點:
給定一數列，並依照題目的移動規則(僅能移動相鄰的數字)由小到大排序，並計算出交換的次數。

解題思路:
一開始看到這題以為是Bubble sort就能解出來殊不知TLE，除了bubble sort之外的sort又好像沒有臨近數字的比較，只好翻解答，結果只需要merge sort就能解題了。
merge sort:
將1數列拆成2個子數列，若2個子數列無法繼續拆則做排序，最後將所有子數列merge起來，時間複雜度N*log(N)。
而該排序法中的其中一個邏輯增加如下
定義:給定2子數列x,y並將其合併 x:(1, 4, 5) y:(2, 3)
1.宣告陣列z存放x,y合併的數列(假設先將x於前,於後y放入該陣列內) z:(1, 4, 5, 2, 3)
2.比較x[0],y[0]，較小者放進x尾端並且較小者index++ z:(1, 4, 5, 2, 3)
3.比較x[1],y[0]，若遇到後放入z的數列較小者，這時候要移動y[0]至z[1]，題目限制只能鄰近數字交換因此需要交換2次，y index++ z:(1, 2, 4, 5, 3)
重複步驟2,3就能排序完並且得到交換的次數

不過其實可以優化，並不需要一開始將x,y放入z也不需要做交換，可以直接計算出交換次數(count)
公式:

 count = z.midIndex - x.currentIndex + 1\\ 
where\ x[currentIndex] > y[currentIndex]\\
Proof:\\
z.midIndex = x.lastIndex \\
=> count = x.lastIndex - x.currentIndex + 1\\
又因交換只會出現於x > y時，而交換次數等於currentIndex - targetIndex，\\
也就是index範圍內的數-1，另外y前方的數字只會是x子數列，這是成為y.currentIndex的條件。\\
因此僅需計算還未比較的x子數列的數量即可(已比較的數字不用計算，因為永遠小於未比較的數)

#include <bits/stdc++.h>
using namespace std;
int merge(vector <int> &input,int left,int mid,int right) {
    vector <int> tmp (right - left + 1, 0);//暫存新排序的數列
    int count = 0;//交換次數
    int mLeft = left;//左邊子數列開始位置
    int mRight = mid + 1;//右邊子數列開始位置
    int m = 0;//暫存數列index
    while(mLeft <= mid && mRight <= right) {
        if(input[mLeft] < input[mRight]) {//左子數列數字 < 右子數列數字
            tmp[m++] = input[mLeft++];
        }
        else if(input[mLeft] > input[mRight]) {//左子數列數字 > 右子數列數字
            tmp[m++] = input[mRight++];
            count += mid - mLeft + 1;
        }
    }
    while(mLeft <= mid) {
        tmp[m++] = input[mLeft++];
    }
    while(mRight <= right) {
        tmp[m++] = input[mRight++];
    }
    for(int i = left; i <= right; i++) {
        input[i] = tmp[i - left];
    }
    return count;
}
int mergeSort (vector <int> &input,int left,int right) {
    int count = 0; 
    int mid = (left + right) / 2;
    if(left < right) {
        count += mergeSort(input, left, mid);//左邊
        count += mergeSort(input, mid + 1, right);//右邊
        count += merge(input,left,mid,right);//merge
    }
    return count;
}
int main () {
    int n = 0;
    while(cin >> n) {
        vector <int> input;
        if(n == 0) {
            break;
        }
        for(int i = 0; i < n; i++) {
            int tmp = 0;
            cin >> tmp;
            input.push_back(tmp);
        }
        mergeSort(input, 0, n - 1) % 2 == 0 ? cout << "Carlos " : cout << "Marcelo ";
        cout << endl;
    }
    return 0;
}

時間複雜度:
mergeSort()=>
N*log(N)

ghost

Filed under: UVA - @ 2021 年 9 月 8 日 下午 1:56

標籤: uva