# 題目: UVa 11495 - Bubbles and Buckets
# 題目說明
你需要將一串有 N 個數字的陣列做排序，每次只能將相鄰的倆倆數字互換
求由 Marcelo 先手， Marcelo 與 Carlos 輪流做一次互換，誰會完成排序？
INPUT:
每筆測資先輸入一個整數 N
接著輸入 N 個數字 (此數字限制範圍為 1 ~ N )
OUTPUT:
輸出 Marcelo 與 Carlos 中誰會勝出 (完成排序)
# 解題方法
讀入資料後，利用 merge sort 將資料做排序
merge sort 的時間複雜度為 O(n*log n)
每次將陣列中的數字分成兩半，直到剩餘一個數字
再比對倆倆子陣列，按照大小排序合併
ans 的方法數為 每次選擇右半邊的陣列時，左半邊剩餘的元素數 的總和
# 參考程式碼
#include <iostream> | |
#include <vector> | |
#include <climits> | |
using namespace std; | |
int ans; | |
// merge sort | |
void merge(vector<int>& P, int front, int mid, int end) | |
{ | |
vector<int> left(P.begin() + front, P.begin() + mid + 1); | |
vector<int> right(P.begin() + mid + 1, P.begin() + end + 1); | |
left.emplace_back(INT_MAX); | |
right.emplace_back(INT_MAX); | |
int l = 0, r = 0; | |
for (int i = front; i <= end; ++i) | |
{ | |
if (left[l] <= right[r]) P[i] = left[l++]; | |
else | |
{ | |
P[i] = right[r++]; | |
ans += left.size() - l - 1; | |
} | |
} | |
} | |
// merge function | |
void mergesort(vector<int>& P, int front, int end) | |
{ | |
if (front < end) | |
{ | |
int mid = (front + end) / 2; | |
mergesort(P, front, mid); | |
mergesort(P, mid + 1, end); | |
merge(P, front, mid, end); | |
} | |
} | |
int main() | |
{ | |
// fast io | |
ios::sync_with_stdio(false); | |
cout.tie(nullptr); | |
cin.tie(nullptr); | |
int N; | |
vector<int> P; | |
while (cin >> N, N) | |
{ | |
P.assign(N + 1, 0); | |
for (int i = 0; i < N; ++i) cin >> P[i]; | |
ans = 0; | |
mergesort(P, 0, N - 1); | |
cout << (ans % 2 ? "Marcelo\n" : "Carlos\n"); | |
} | |
return 0; | |
} |
# 參考資料
https://blog.csdn.net/mobius_strip/article/details/8217669
https://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html
https://sites.google.com/site/zsgititit/home/jin-jiec-cheng-shi-she-ji/uva-11495---bubbles-and-buckets
