抱歉，您的瀏覽器無法訪問本站
本頁面需要瀏覽器支持（啟用）JavaScript
了解詳情 >

UVa 10810 - Ultra-QuickSort

UVa

2019年9月17日

題目簡述

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

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

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

    解題想法

  • 使用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;
}

C/C++

UVa

Sort

Merge Sort

評論




@2018-2021 By Willy Chen

本站使用 Volantis 作為主題