【解題】Zerojudge f832: 隕石 (Meteorite)

發布於 更新於 分類於 ， 閱讀次數： 文章字數： 366 所需閱讀時間 ≈ 1 分鐘

題目連結

f832: 隕石 (Meteorite)

我的想法

貪婪演算法（Greedy），每一步都使用最佳的解，從而導致希望結果也是最佳的解。

就範例二而言

1
2
3
4 4
1 8 5 7
1 9 6 6

機器之間或隕石之間，又或者是機器與隕石間無任關聯，我們將他們排序

1
2
1 5 7 8
1 6 6 9

當機器可抓取的最大能力是 9，先找到能符合小於 9 的對大數字是 8（此時就是這一步的最佳解），sum += 8，並且換另一台機器。
當機器可抓取的最大能力是 6，先找到能符合小於 6 的對大數字是 5（此時就是這一步的最佳解），sum += 5，並且換另一台機器。
當機器可抓取的最大能力是 6，先找到能符合小於 6 的對大數字是 1（此時就是這一步的最佳解），sum += 1，並且換另一台機器。
沒石頭可以抓，輸出 sum，結束程式。

:::warning
總和會大於 2^32，故 sum 要使用 long long
:::

參考解答

f832
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    long long rock[n], robot[m];
    for (int i = 0; i < n; i++) cin >> rock[i];
    for (int i = 0; i < m; i++) cin >> robot[i];
    sort(rock, rock + n);
    sort(robot, robot + m);

    long long sum = 0;
    int index_bot = m - 1;
    for (int i = n - 1; i >= 0 && index_bot >= 0; i--) {
        if (robot[index_bot] >= rock[i]) {
            sum += rock[i];
            index_bot--;
        }
    }
    cout << sum << "\n";
    return 0;
}