c904: 天龍國的蜜蘋果
標籤 :
通過比率 : 11人/17人 ( 65% ) [非即時]
評分方式:
Tolerant

最近更新 : 2018-12-12 08:05

內容
天龍國生產一種蜜蘋果,體積碩大,甜度破表,是其國家主要的收入來源。每一顆蘋果的重量(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 位)
範例輸入
3 2
5 5
10 7
8 6
2
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
提示 :
二分搜尋
標籤:
出處:
林口高中校內選訓 [編輯:
hshua (hshua)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」