f832.
隕石 (Meteorite)
內容
問題敘述
有 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, …, CN ≤ 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
不公開 測資點#0 (5%): 1.0s , <1K
不公開 測資點#1 (5%): 1.0s , <1K
不公開 測資點#2 (5%): 1.0s , <1K
不公開 測資點#3 (5%): 1.0s , <1K
不公開 測資點#4 (5%): 1.0s , <1M
不公開 測資點#5 (5%): 1.0s , <1M
不公開 測資點#6 (5%): 1.0s , <1M
不公開 測資點#7 (5%): 1.0s , <1M
不公開 測資點#8 (5%): 1.0s , <1M
不公開 測資點#9 (5%): 1.0s , <1M
不公開 測資點#10 (5%): 1.0s , <1M
不公開 測資點#11 (5%): 1.0s , <1M
不公開 測資點#12 (5%): 1.0s , <1M
不公開 測資點#13 (5%): 1.0s , <10M
不公開 測資點#14 (5%): 1.0s , <1M
不公開 測資點#15 (5%): 1.0s , <1M
不公開 測資點#16 (5%): 1.0s , <10M
不公開 測資點#17 (5%): 1.0s , <1M
不公開 測資點#18 (5%): 1.0s , <1M
不公開 測資點#19 (5%): 1.0s , <1M
不公開 測資點#0 (5%): 1.0s , <1K
不公開 測資點#1 (5%): 1.0s , <1K
不公開 測資點#2 (5%): 1.0s , <1K
不公開 測資點#3 (5%): 1.0s , <1K
不公開 測資點#4 (5%): 1.0s , <1M
不公開 測資點#5 (5%): 1.0s , <1M
不公開 測資點#6 (5%): 1.0s , <1M
不公開 測資點#7 (5%): 1.0s , <1M
不公開 測資點#8 (5%): 1.0s , <1M
不公開 測資點#9 (5%): 1.0s , <1M
不公開 測資點#10 (5%): 1.0s , <1M
不公開 測資點#11 (5%): 1.0s , <1M
不公開 測資點#12 (5%): 1.0s , <1M
不公開 測資點#13 (5%): 1.0s , <10M
不公開 測資點#14 (5%): 1.0s , <1M
不公開 測資點#15 (5%): 1.0s , <1M
不公開 測資點#16 (5%): 1.0s , <10M
不公開 測資點#17 (5%): 1.0s , <1M
不公開 測資點#18 (5%): 1.0s , <1M
不公開 測資點#19 (5%): 1.0s , <1M
提示 ：
評分說明
第一組 20 分 N , M ≤ 10, N = M, W 1 , …, W N ≤ 102
第二組 40 分 N , M ≤ 103
第三組 40 分 無特別限制
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 31823 |
|
f832 | 445 | 2022-08-21 23:14 |