2011年10月19日 星期三

97模擬 Problem 7 (奧步戰術

在黑暗算法界中，使用奧步解題似乎已經漸漸成為主流。雖然使用奧步將漸漸使人走向魔路，最後被內心的虛無吞噬，不過這不是今天的問題。考慮在某個考試中，有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＜， T≤1000000000

輸出說明：
每個測試範例請輸出一個整數，代表最大得分。

輸入範例：
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
張貼者： 於

2 則留言:

  1. 匿名2011年10月20日 下午3:05

    Dim X()
    Dim Y()
    Private Sub Form_Load()
    Me.Hide
    Open App.Path & "\in.txt" For Input As #1
    Open App.Path & "\out.txt" For Output As #2
    Input #1, N
    For i = 1 To N
    Input #1, N2, T
    ans = 0
    ReDim X(N2): ReDim Y(N2)
    For j = 1 To N2
    Input #1, X(j), Y(j)
    Next j

    For j = 1 To N2 - 1
    For r = j + 1 To N2
    If X(j) > X(r) Then
    D = X(j)
    X(j) = X(r)
    X(r) = D
    D = Y(j)
    Y(j) = Y(r)
    Y(r) = D
    End If
    Next r
    Next j

    For j = 1 To N2
    If (Y(j) / X(j)) <= (1 / 2) And T >= Y(j) Then X(j) = 1000001: ans = ans + 1: T = T - Y(j)
    Next j

    For j = 1 To N2
    If X(j) <> 1000001 And T >= X(j) Then ans = ans + 2: T = T - X(j)
    Next j

    Print #2, ans

    Next i
    Close #2
    Close #1
    End
    End Sub

    回覆刪除
  2. Arro2011年10月21日 上午11:39

    Dim x(), y(), ans, n, AA
    Private Sub Form_Load()
    Me.Hide
    Open App.Path & "\in.txt" For Input As #1
    Open App.Path & "\out.txt" For Output As #2

    Input #1, t
    For i = 1 To t
    Input #1, m, n
    ReDim x(m), y(m)
    For j = 1 To m
    Input #1, x(j), y(j)
    Next
    Call A1
    Call A11
    Call A2

    Next
    Close
    Close
    End
    End Sub

    Sub A1()
    For j = 1 To UBound(x)
    For i = 1 To UBound(x) - 1
    If x(i) > x(i + 1) Then
    t3 = x(i): t4 = y(i)
    x(i) = x(i + 1): y(i) = y(i + 1)
    x(i + 1) = t3: y(i + 1) = t4
    End If
    Next
    Next
    End Sub


    Sub A11()
    For j = 1 To UBound(x)
    For i = 1 To UBound(x) - 1
    If x(i) = x(i + 1) And y(i) > y(i + 1) Then
    t4 = y(i)
    y(i) = y(i + 1)
    y(i + 1) = t4
    End If
    Next
    Next

    End Sub


    Sub A2()
    AA = 0
    ans = 0

    For i = 1 To UBound(x)
    If ans + x(i) <= n Then ans = ans + x(i): AA = AA + 2 Else If ans + y(i) <= n Then ans = ans + y(i): AA = AA + 1
    If ans = n Then Exit For
    Next

    Print #2, AA
    End Sub

    回覆刪除

訂閱： 張貼留言 (Atom)