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

賽前測試題目

PROBLEM 4 Sort

Program file	SORT.EXE
Input file	SORT.IN
Output file	SORT.OUT
Execution time	30 s

資訊系研究自然語言，後來發現叫每個人找不同字母開頭的字，不如叫每個人找不同種類的單字。所以，在每個人的陣列中，會有不同字母開頭的單字，必須用以下的程式合併陣列。這個程式有個特性，就是任意順序合併陣列，新的陣列都會保持排序。


SUB merge (DET() AS STRING, SRC1() AS STRING, SRC2() AS STRING)
Ptr = 1: Ptr1 = 1: Ptr2 = 1
DO WHILE Ptr1 <= UBOUND(SRC1) AND Ptr2 <= UBOUND(SRC2)
	SELECT CASE SRC1(Ptr1)   ' 迴圈直到其中一個陣列讀完為止
	CASE IS < SRC2(Ptr2)
		DET(Ptr) = SRC1(Ptr1): Ptr1 = Ptr1 + 1
	CASE IS > SRC2(Ptr2)
		DET(Ptr) = SRC2(Ptr2): Ptr2 = Ptr2 + 1
	CASE IS = SRC2(Ptr2)
		DET(Ptr) = SRC1(Ptr1): Ptr1 = Ptr1 + 1: Ptr2 = Ptr2 + 1
	END SELECT
	Ptr = Ptr + 1
LOOP
FOR Ptr1 = Ptr1 TO UBOUND(SRC1)  ' 以下二個迴圈至多一個會成功執行
	DET(Ptr) = SRC1(Ptr1): Ptr = Ptr + 1
NEXT
FOR Ptr2 = Ptr2 TO UBOUND(SRC2)
	DET(Ptr) = SRC2(Ptr2): Ptr = Ptr + 1
NEXT
END SUB

輸入檔和前一題類似，每一組測試資料中，第一行為數字 N ，表示有 N 個陣列，接下來一行有 N 個數字 S1 到 SN ，表示陣列的大小。接下來是下組測試資料，讀到 N = 0 表示檔案結束。請算出合併所需最少的時間，印到輸出檔中。合併所需的時間，以合併後的大小計算。數字都為正整數，N<=10000 ， Si<=9 (i=1..N)。

範例﹕

SORT.IN

4 2 2 5 2 4 5 2 2 2 0

SORT.OUT

21 21

提示﹕

答案會超過 32767 。

前一題第三個圖在本題中是合於本題規則的。