c904.
天龍國的蜜蘋果
內容
天龍國生產一種蜜蘋果，體積碩大，甜度破表，是其國家主要的收入來源。每一顆蘋果的重量(w)不一樣，因甜度不同而售價(v)也有所不同，
今有 N 個蘋果，試求從中任意取出 K 個蘋果，使其<單位重量的售價>為最大。
<單位重量的售價> = <K 個蘋果的售價總和> / <K 個蘋果的重量總和>
範例: N=3, M=2, {w,v} --> {(5,5), (10,7), (8,6)}
k=2
選 (5,5)、(8,6) 兩個 --> (5+6)/(5+8)≅0.85 為最大值
k=1
選 (5,5) --> 5/5=1.00 為最大值
輸入說明
測資第一行為整數 N、M，代表有 N 個蘋果，接下來有 N 行，每行兩個整數(w、v)代表蘋果的重量與售價，
接下來有 M 行，每行一個整數 K。
(2<=N,K<=1000, 1<=M<=50)
輸出說明
輸出 M 行，每行對應一個 K 的結果。 (小數點後 2 位)
範例輸入
#1
3 2 5 5 10 7 8 6 2 1
範例輸出
#1
0.85 1.00
測資資訊：
記憶體限制：
512
MB
不公開 測資點#0 (25%): 1.0s , <1K
不公開 測資點#1 (25%): 1.0s , <1K
不公開 測資點#2 (25%): 1.0s , <1K
不公開 測資點#3 (25%): 1.0s , <1M
不公開 測資點#0 (25%): 1.0s , <1K
不公開 測資點#1 (25%): 1.0s , <1K
不公開 測資點#2 (25%): 1.0s , <1K
不公開 測資點#3 (25%): 1.0s , <1M
提示 ：
二分搜尋
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||