技藝競竇95年模擬試題參考答案 Q2 (過橋問題)

'  二、過橋問題 (15%)
'  有n個人想要在晚上過橋，橋上每次最多只能容許兩個人行走。由於全部只有一支手電筒，
'  所以每次兩個人拿著手電筒過橋後，必須有一人再把手電筒拿回來，這樣後面的人才能繼續過橋。 
'  每個人走路的速度不同，過橋所需的時間也因此不同。而每次過橋的那兩個人，其花費的時間以較慢的那個人計算
'  （走的快的當然要等走的慢的，因為只有一支手電筒）。你的任務是寫一個程式，安排這n個人過橋，
'  並使得總共花費的時間最少。 
'  輸入規範
'  輸入檔案的第一列有一個正整數，代表以下有多少組測試資料。每組測試資料的第一列有1個整數n，
'  代表要過橋的人數（最多不會超過1000人）。接下來的n列，每列有1個整數，代表這n個人過橋所需的時間（秒），
'  這些時間均不會超過100秒。 
'  輸入的第一列與第一組測試資料之間，以及各組測試資料之間均有一空白列（請參考輸入範例）。
'  輸出規範
'  每組測試資料輸出的第一列為一個整數，代表這組中n個人過橋所需的最少時間。
'  接下來的列為達到此最少時間的過橋方式。每列有1個或2個整數代表過橋的人
' （每個人以其過橋所需的時間代表。雖然可能有2人過橋時間相同，但那並不會影響結果）。
'  請注意，過橋的順序是去、回交替的，因為需有一人把手電筒帶回。
'  以第一組輸出為例說明：最少需17秒才能讓這4個人過橋。
'  方式為：1秒、2秒的人先過橋，1秒的回來，5秒、10秒的過橋，2秒的回來，最後1秒、2秒的過橋，
'  所以總共的時間為：2+1+10+2+2=17。 
'  如果有不止一種方式可以達到最少時間，輸出任何一種均可。輸出資料的組間亦請空一列。
'  輸入範例（test2.txt）
'  2

'  4
'  1
'  2
'  5
'  10

'  4
'  1
'  98
'  99
'  100
'  輸出範例（result2.txt）
'  17
'  1 2
'  1
'  5 10
'  2
'  1 2

'  299
'  1 100
'  1
'  1 99
'  1
'  1 98


'  過橋問題不限定人數版

Public Class Form1
    Dim dlist As New ArrayList
    Dim slist As New ArrayList
    Dim resultStr = ""
    Dim resultStr1 = ""
    Dim total = 0

    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Me.Hide()
        Dim fileContents As String
        fileContents = My.Computer.FileSystem.ReadAllText(Application.StartupPath & "\Test2.txt")
        Dim recArray = Split(fileContents, vbNewLine)
        Dim ternN = Val(recArray(0))

        Dim recIndex = 2
        For j As Integer = 1 To ternN
            Dim dataN = Val(recArray(recIndex))

            For i As Integer = 1 To dataN
                slist.Add(Val(recArray(recIndex + i)))
            Next
            slist.Sort()

            total = 0
            resultStr = ""

            bridge(slist, dlist, slist.Count)

            resultStr = total & vbNewLine & resultStr
            resultStr1 = resultStr1 & resultStr & vbNewLine

            recIndex = recIndex + dataN + 1 + 1
        Next
        'MsgBox(resultStr1)
        My.Computer.FileSystem.WriteAllText(Application.StartupPath & "\result2.txt", resultStr1, False)
        End
    End Sub

    Sub bridge(ByVal slist, ByVal dlist, ByVal n)
        If n = 2 Then
            slist.sort()
            resultStr = resultStr & slist(0) & " " & slist(1) & vbNewLine
            total = total + IIf(slist(0) > slist(1), slist(0), slist(1))
            dlist.Add(slist(0))
            dlist.Add(slist(1))
            slist.Remove(slist(1))
            slist.Remove(slist(0))
        Else
            slist.Sort()
            If n = 3 And (slist(2) - slist(1)) > (slist(1) - slist(0)) Then
                slist.Reverse()
                resultStr = resultStr & slist(1) & " " & slist(0) & vbNewLine
            Else
                resultStr = resultStr & slist(0) & " " & slist(1) & vbNewLine
            End If
            total = total + IIf(slist(0) > slist(1), slist(0), slist(1))
            dlist.Add(slist(0))
            dlist.Add(slist(1))
            slist.Remove(slist(1))
            slist.Remove(slist(0))
            dlist.Sort()
            resultStr = resultStr & dlist(0) & vbNewLine
            total = total + dlist(0)
            slist.Add(dlist(0))
            dlist.Remove(dlist(0))
            bridge(slist, dlist, n - 1)
        End If
    End Sub
End Class