f832. 隕石 (Meteorite)
標籤 : greedy
通過比率 : 313人/377人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-05-07 20:45

內容

問題敘述
有 N 顆隕石即將要掉落在 OI 國,所幸科學家預測隕石的著陸位置是在杳無人煙的荒野上,即使著陸也不會造成傷亡。科學家發現這一批隕石上面含有一種稀有而且 OI 國迫切需要的物質,因而想要去提煉。然而,如果在隕石撞進地表後再去開挖,需要花費很長的時間;在唯一的解法是要使用一種特殊的隕石捕捉器在空中攔截,然後帶回實驗室。


已知 OI 國有 M 個隕石捕捉器,每一個捕捉器只能使用一次,而且只可捕捉一個隕石。第 i 個捕捉器可以捕捉一個重量不超過Ci單位重的隕石。N 顆隕石的重量已由科學家估算出來,重量分別為 W1 ~ WN
一個隕石上稀有物質的含量正比於該隕石的重量,所以 OI 國 的目標是要最大化捕捉隕石的重量總和。給定隕石重量以及捕捉器的容量,請寫一個程式計算 OI 國的科學家最多能捕捉到重量總和為多少的隕石。

輸入說明

第一行有兩個正整數 N 和 M 分別表示有 N 顆隕石 和 M 個隕石捕捉器。

第二行有 N 個正整數 W1, …, WN,整數後以一個空白隔開,表示每一個隕石的重量。第三行有 M 個正整數 C1, …, CM,整數後以一個空白隔開,第 i 個數表示每一個隕石捕捉器最多可以捕捉到重量為 Ci的隕石 。

1 ≤ N, M ≤ 105

1 ≤ W1 , …, WN ≤ 109

1 ≤ C1, …, C≤ 109

輸出說明

請輸出一行正整數,表示科學家最大能捕捉隕石的重量總和。答案有可能會超過 32 位元有號整數的範圍。

範例輸入 #1
4 3
23 45 67 99 
46 67 100 
範例輸出 #1
211
範例輸入 #2
4 4
1 8 5 7 
1 9 6 6 
範例輸出 #2
14
測資資訊:
記憶體限制: 256 MB
提示 :

評分說明
第一組 20 分 N , M ≤ 10, N = M, W 1 , …, W N ≤ 102
第二組 40 分 N , M ≤ 103
第三組 40 分 無特別限制

標籤:
greedy
出處:
TOI練習賽202012潛力組第一題 [管理者: fire5386 (becaidorz) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
31823 a011190@stdm ... (46 邱泓愷Kyle) f832
c++解答
570 2022-08-21 23:14