c904: 天龍國的蜜蘋果
Tags :
通过比率 : 56% (5 人 / 9 人 ) (非即時)
評分方式:
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
提示 :
二分搜尋
Tags:
出處:
林口高中校內選訓 [編輯:
hshua (hshua)
]


编号 身分 题目 主题 人气 发表日期
沒有發現任何「解題報告」