題目簡述

  • 輸入一串數字,要把其從小到大排列

  • 每個數字可以和其左右鄰居的數字進行交換

  • 輸出最少的交換次數,讓這串數字排列好

    解題想法

  • 使用Bubble Sort來實作,只要計算左右數字交換了幾次,然後輸出答案就可以了,但是因為時間複雜度是 $O(n^2)$ ,非常有可能會TLE

  • 這題的題目雖然命名為Quick Sort,但實際上是用Merge Sort來排序

  • 使用Merge Sort來實作,時間複雜度是 $O(nlogn)$ ,再來就是想怎麼計算交換次數了

  • 考慮以下Merge時的狀況:

    Index 0 1 2 3 4 5
    Value 2 5 6 3 4 7
    • 假設 Index 0~2 是左陣列, 3~5 是右陣列

    • 第一輪因為 value 2 是最小的,因此不用動

      Index 0 1 2 3 4 5
      Value 2 5 6 3 4 7
      Merge 2
    • 第二輪右陣列的 value 3 是最小的,因此要往左交換(換句話說, value 5 和 6 會往後排),要交換的次數就是左陣列剩下還沒排的2個數字, counter=2

      Index 0 1 2 3 4 5
      Value 2 5 6 3 4 7
      Merge 2 3
    • 第三輪右陣列的 value 4 是最小的,因此要往左交換,要交換的次數就是左陣列剩下還沒排的2個數字, counter=2+2=4

      Index 0 1 2 3 4 5
      Value 2 5 6 3 4 7
      Merge 2 3 4
    • 第四輪左陣列的 value 5 是最小的,因此不需要進行交換,直接放進去, counter=4

      Index 0 1 2 3 4 5
      Value 2 5 6 3 4 7
      Merge 2 3 4 5
    • 第五輪左陣列的 value 6 是最小的,因此不需要進行交換,直接放進去, counter=4

      Index 0 1 2 3 4 5
      Value 2 5 6 3 4 7
      Merge 2 3 4 5 6
    • 第六輪右陣列的 value 7 是最小的,但是因為左陣列已經沒數字了,因此不需要進行交換,直接放進去, counter=4

      Index 0 1 2 3 4 5
      Value 2 5 6 3 4 7
      Merge 2 3 4 5 6 7
  • counter要計算的,就是當Merge時要放右陣列的數字時,counter要加上左陣列剩下數字的數量

  • 所以要做的事情就是實作Merge Sort,然後加上counter計算次數

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*****************************************
Filename:p10810.cpp
Author:Willy Chen(willychen.org)
Date:2019.09.17
*****************************************/
#include<iostream>
using namespace std;

long long int counter;
int ans[500005]={0};

void Merge(int* input, int left, int mid, int right){
int idxl=left,idxr=mid+1;

for(int i=0;i<=right-left;++i){
if(idxl>mid){
/* Left array run out */
ans[i]=input[idxr++];
continue;
}
if(idxr>right){
/* Right array run out */
ans[i]=input[idxl++];
continue;
}
if(input[idxl]<=input[idxr]){
/* Copy left array value */
ans[i]=input[idxl++];
}else{
/* Copy right array value */
counter += (mid-idxl+1);
ans[i]=input[idxr++];
}
}

/* Copy to original array */
for(int i=0;i<=right-left;++i){
input[left+i]=ans[i];
}
}

void mergeSort(int* input, int left, int right){
if(left<right){
int mid = (left+right)/2;
/* Split left array */
mergeSort(input, left, mid);
/* Split right array */
mergeSort(input, mid+1, right);
/* Merge left and right array */
Merge(input, left, mid, right);
}
}

int main(){
int kase;
while(1){
cin >> kase;
if(kase==0)
break;
else{
int input[500005]={0};
for(int i=0;i<kase;++i){
cin >> input[i];
}
counter = 0;
mergeSort(input,0,kase-1);
cout << counter<< endl;
}
}
return 0;
}

評論

 無法加載Disqus評論系統,請確保您的網絡能夠正常訪問。



本站使用 Volantis 作為主題