CSES 问题集公寓：请提示解决其余问题

Question

有 n 个申请人，m 个空闲公寓。您的任务是分配公寓，以便尽可能多的申请人获得公寓。 每个申请人都有一个想要的公寓面积，他们会接受任何面积足够接近所需面积的公寓。 输入 第一输入行有三个整数n、m和k：申请人数、公寓数和最大允许差异。 下一行包含 n 个整数 a_1, a_2, ..., a_n：每个申请人所需的公寓面积。如果申请人所需的面积为x，则他或她将接受面积在x-k和x+k之间的任何公寓。 最后一行包含 m 个整数 b_1, b_2, ..., b_m：每个公寓的大小。 输出 打印一个整数：将获得公寓的申请人数。 限制

1 小于或等于 n，m 小于或等于 2 * 10^5 0 小于或等于 kl ess 小于或等于 10^9 1 小于或等于a_i, b_i 小于或等于10^9

示例 输入： 4 3 5 60 45 80 60 30 60 75

输出： 2

到目前为止我的尝试：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int m;
    int n;
    int k;
    cin >> n >> m >> k;
    multiset<int> desired;
    multiset<int> actual;
    int input;

    for (int i = 0; i < n; i++)
    {
        cin >> input;
        desired.insert(input);
    }
    for (int i = 0; i < m; i++)
    {
        cin >> input;
        actual.insert(input);
    }
}

到目前为止，我已经接受了 n、m 和 k 的输入。然后，我获取第二行输入，即所需的公寓大小，并将它们存储在名为“desired”的多重集中。然后，我对实际公寓大小进行了相同的操作，并将它们存储在名为“actual”的多重集中。我不知道从这里该怎么做:(。请给我一个解决问题的提示吗？

Answer 1

首先，第一件事

• 使用它是一个不好的做法：

#include <bits/stdc++.h>
using namespace std;

• 我们这里不需要

  std::multiset

  。只需使用

  std::vector

  。

代码

#include <iostream>
#include <vector>
#include <algorithm>

static const int solve(
    int n,
    int m,
    int k,
    std::vector<int> &applicants,
    std::vector<int> &apartments)
{
    std::sort(std::begin(applicants), std::end(applicants));
    std::sort(std::begin(apartments), std::end(apartments));

    int res = 0;
    int j = 0;

    for (int i = 0; i < n; ++i)
    {
        while (j < m && apartments[j] < applicants[i] - k)
        {
            ++j;
        }
        if (j < m && apartments[j] <= applicants[i] + k)
        {
            ++res;
            ++j;
        }
    }

    return res;
}

int main()
{
    int n = 4, m = 3, k = 5;

    std::vector<int> A = {60, 45, 80, 60};
    std::vector<int> B = {30, 60, 75};

    std::cout << solve(n, m, k, A, B);

    return 0;
}