c904: 天龍國的蜜蘋果
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 為 最 大 值
天 龍 國 生 產 一 種 蜜 蘋 果 ， 體 積 碩 大， 甜 度 破 表 ， 是 其 國 家 主 要 的 收 入 來源 。 每 一 顆 蘋 果 的 重 量 ( 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 為 最 大 值
solve :
不 行 用 貪 心。
最 大 化 平 均 值。
code:
留言
張貼留言