1 solutions

  • 0
    @ 2025-5-16 14:42:38

    本题是一个经典的贪心问题。

    我们不妨把钱从大到小排序。

    那么最大的钱一定去买最贵的物品(如果能买的)。

    如果不能买,那么这个最贵的物品就不可能被买走,直接跳过即可。

    #include <bits/stdc++.h>
    using namespace std;
    long long w[1000000 + 10];
    long long c[1000000 + 10];
    int main() {
        long long n, m;
        long long ans = 0;
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) {
            cin >> w[i];
        }
        for (int i = 1; i <= m; ++i) {
            cin >> c[i];
        }
        sort(w + 1, w + n + 1);
        sort(c + 1, c + m + 1);
        int i = n;
        int j = m;
        while (i >= 1 && j >= 1) {
            if (w[i] >= c[j]) {
                i--;
                j--;
                ans++;
            } else {
                j--;
            }
        }
        cout << ans;
        return 0;
    }
    

    Information

    ID
    662
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    8
    Tags
    (None)
    # Submissions
    59
    Accepted
    10
    Uploaded By