2012年8月30日 星期四

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
張貼者： 於

4 則留言:

  1. 匿名2012年8月30日 晚上7:54

    Private Sub Form_Load()
    Me.Hide
    Dim a(), b() As Integer
    Open App.Path & "\in.txt" For Input As #1
    Open App.Path & "\out.txt" For Output As #2
    Input #1, n
    For k = 1 To n
    Input #1, x, t
    ReDim a(x), b(x)
    ans = 0
    For i = 1 To x
    Input #1, h, c
    a(i) = h
    b(i) = c
    Next
    For i = 1 To x
    For j = 1 To x - 1
    If a(j) > a(j + 1) Then
    c = a(j)
    a(j) = a(j + 1)
    a(j + 1) = c
    c = b(j)
    b(j) = b(j + 1)
    b(j + 1) = c
    End If
    Next
    Next
    For i = 1 To x
    If (1 / 2) >= (b(i) / a(i)) And b(i) <= t Then ans = ans + 1: t = t - b(i): a(i) = 0
    Next
    For i = 1 To x
    If a(i) <> 0 And a(i) <= t Then ans = ans + 2: t = t - a(i)
    Next
    Print #2, ans
    Next
    Close
    Close
    End
    End Sub

    回覆刪除
  2. 吾存在2012年10月13日 晚上11:00

    請問一下，用你的這種方式做
    如果時間給很大，以至於可以全部用2分作答也還有剩餘時間的話
    那該寫法不就不成立了?
    by.正在思考著這題的路克

    回覆刪除
  3. 匿名2012年10月14日 上午9:43

    我沒想過這個問題！
    這樣的話就會不成立了。

    回覆刪除
  4. 匿名2012年10月14日 上午9:48

    但是這個問題只要加上一個判斷就解決了。
    Private Sub Form_Load()
    Me.Hide
    Dim a(), b() As Integer
    Open App.Path & "\in.txt" For Input As #1
    Open App.Path & "\out.txt" For Output As #2
    Input #1, n
    For k = 1 To n
    Input #1, x, t
    ReDim a(x), b(x)
    ans = 0
    For i = 1 To x
    Input #1, h, c
    a(i) = h
    b(i) = c
    Next
    For i = 1 To x
    For j = 1 To x - 1
    If a(j) > a(j + 1) Then
    c = a(j)
    a(j) = a(j + 1)
    a(j + 1) = c
    c = b(j)
    b(j) = b(j + 1)
    b(j + 1) = c
    End If
    Next
    Next
    sumh = 0
    For i = 1 To x
    sumh = a(i) + sumh
    Next
    If sumh > t Then
    For i = 1 To x
    If (1 / 2) >= (b(i) / a(i)) And b(i) <= t Then ans = ans + 1: t = t - b(i): a(i) = 0
    Next
    For i = 1 To x
    If a(i) <> 0 And a(i) <= t Then ans = ans + 2: t = t - a(i)
    Next
    Print #2, ans
    Else
    Print #2, x * 2
    End If
    Next
    Close
    Close
    End
    End Sub

    回覆刪除

訂閱： 張貼留言 (Atom)