技藝競竇97年模擬試題參考答案 Q7

'  Problem7：奥步戰術(17%)
'  在黑暗算法界中，使用奧步解題似乎已經漸漸成為主流。雖然使用奧步將漸漸使人走向魔路，最後被內心的虛無吞
'  噬，不過這不是今天的問題。考慮在某個考試中，有n 道題目，而總答題時間為T。對於每題都只有三種可能：
'  1. 正解能得到全對的分數(得2 分)
'  2. 奧步能拿到半對(得1 分)
'  3. 放棄的話當然就沒分囉(0 分)
'  而對每題來說，要達到這三種分數所需花的時間皆不同，所有題目拿0 分都不用花費時間；在題目i 使用奧步拿半
'  對所需時間為Hi，要寫正解所需時間為Ci ，其中對於任何題目i，必有滿足0'  試問：在時間T 內，用最佳的答題方式，最多可以拿幾分？
'  輸入說明：
'  輸入檔第一行說明有幾組測試資料，第二行有兩個整數n 和T，分別代表有幾題，以及總作答時間。接下來n 行每
'  行有兩個整數Ci 和Hi，代表第i 題寫正解需要時間Ci，寫奧步需要時間Hi。其中：
'   題目總數n≤100000
'   答題所需時間1≤Hi，Ci≤1000000
'   總作答時間0'  輸出說明：
'  每個測試範例請輸出一個整數，代表最大得分。
'  輸入範例：
'  2
'  5 12
'  4 3
'  6 2
'  5 3
'  4 3
'  5 2
'  4 10
'  5 3
'  6 5
'  3 1
'  4 3
'  輸出範例：
'  6
'  5


Structure recData
    Dim c As Integer
    Dim h As Integer
    Dim cR As Single
    Dim hR As Single
    Dim isC As Boolean
    Dim isUsed As Boolean
End Structure
Public Class Form1
    ' Dim debugStr = ""
    Dim resultStr = ""
    Dim score = 0
    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Me.Hide()
        Dim a(100000) As recData
        Dim fileContents As String
        fileContents = My.Computer.FileSystem.ReadAllText(Application.StartupPath & "\Test7.txt")
        Dim recArray() = Split(fileContents, vbNewLine)
        Dim recN = Val(recArray(0))

        Dim recIndex = 1
        For j As Integer = 1 To recN
            'read data for one turn
            Dim dataArray = Split(recArray(recIndex), " ")
            Dim dataN = Val(dataArray(0))
            Dim t = Val(dataArray(1))
            For i = 1 To dataN
                dataArray = Split(recArray(recIndex + i))
                a(i).c = Val(dataArray(0))
                a(i).h = Val(dataArray(1))
                a(i).cR = 2 / a(i).c
                a(i).hR = 1 / a(i).h
                a(i).isC = True
                a(i).isUsed = False
            Next
            'proc one turn
            
            Dim c = 1
            While t > 0 And c <= dataN
                'find the max
                Dim pMax As Single = 0
                Dim maxIndex = 0
                For i3 = 1 To dataN
                    If a(i3).cR > pMax And a(i3).isUsed = False Then
                        pMax = a(i3).cR
                        maxIndex = i3
                    End If
                Next
                For i3 = 1 To dataN
                    If a(i3).hR > pMax And a(i3).isUsed = False Then
                        pMax = a(i3).hR
                        maxIndex = i3
                        a(i3).isC = False
                    End If
                Next

                'accmulate score and subtract the time
                If a(maxIndex).isC = True Then
                    t = t - a(maxIndex).c
                    score = score + 2
                    'debugStr = debugStr & a(maxIndex).c & a(maxIndex).h & "C" & vbNewLine
                Else
                    t = t - a(maxIndex).h
                    score = score + 1
                    ' debugStr = debugStr & a(maxIndex).c & a(maxIndex).h & "H" & vbNewLine
                End If
                a(maxIndex).isUsed = True

                c = c + 1
            End While
            ' MsgBox(debugStr)
            resultStr = resultStr & score & vbNewLine

            ' clear data for next turn
            ReDim a(100000)
            score = 0
            recIndex = recIndex + dataN + 1
        Next

        MsgBox(resultStr)
        'My.Computer.FileSystem.WriteAllText(Application.StartupPath & "\result7.txt", resultStr, False)
        End
    End Sub
End Class