網際網路程式設計全國大賽

賽前測試題目

PROBLEM 3 Merge

DEFINT A-Z
SUB merge (DET() AS STRING, SRC1() AS STRING, SRC2() AS STRING)
Ptr = 1                                         ' 將SRC1()和SRC2()合併到DET()
FOR i = 1 TO UBOUND(SRC1)                       ' 先把SRC1()的資料複製到DET()中
        DET(Ptr) = SRC1(i)
        Ptr = Ptr + 1
NEXT
FOR i = 1 TO UBOUND(SRC2)                       ' 再把SRC2()的資料加到DET()中
        DET(Ptr) = SRC2(i)
        Ptr = Ptr + 1
NEXT
END SUB

這個副程式執行所需要的時間正比於 SRC1() 和 SRC2() 合併後的大小。很多陣列要合併時， 不同的合併順序，將會導致不同的執行時間。這一題要寫一個程式，算出不同順序下， 最少需要的時間。

現將問題一般化，收集到的陣列不一定是 26 個。設輸入檔的每一組測試中，第一個數字為 N ， 表示有 N 個陣列需要合併，接下來的一行，有 N 個數字 S1 到 SN ，表示陣列的大小， 都照開頭字母順序排好(例如第一個陣列是 A 開頭的，第二個陣列是 B 開頭的...)。接下來會 是下一組測試資料，直到 N = 0 表示檔案結束。合併所需的時間，以合併後的大小來表示。請將 答案輸出到檔案中。不過，請注意合併的順序，每次都會是相鄰的陣列合併，才會使新的陣列資 料保持排序。數字都為正整數，N<=80，Si<=9 (i=1..N)。

範例﹕

MERGE.IN 4 2 2 3 3 4 3 3 2 2 0

MERGE.OUT 20 20

提示﹕

N 個陣列可能的合併方法共有
。

前面的程式，要在 SRC1() 中的資料都小於 SRC2() 中的資料才能合併出保持排序的資料。

舉例說明如何計算合併所需的時間。

資料﹕2 3 4 3 2