题解 | #六一儿童节# 贪心

将两个数组排序后，采用贪心策略，能分则分

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, tmp;
    vector<int> h, w;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        h.push_back(tmp);
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> tmp;
        w.push_back(tmp);
    }
    sort(h.begin(), h.end());
    sort(w.begin(), w.end());
    int ans = 0;
    for (int i = 0, j = 0; i < n && j < m; j++) {
        // 符合大小要求后，分配一块巧克力，并遍历下一个小朋友
        if (w[j] >= h[i]) {
            ans++;
            i++;
        }
    }
    cout << ans << endl;
    return 0;
}

时间复杂度：O(nlogn + mlogm)，其中 n 为小朋友的数量，m 为巧克力的数量。主要时间消耗在对两个数组进行排序上

空间复杂度：空间复杂度为 O(n + m)，主要是用来存储小朋友的要求和巧克力的大小