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 小于或等于 k 小于或等于 10^9， 1小于或等于a_i，b_i小于或等于10^9。

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

输出： 2

到目前为止我的尝试：

#include <iostream>
#include <vector>

using std::cout;
using std::cin;

int main()
{
    int m;
    int n;
    int k;
    cin >> n >> m >> k;
    vector<int> desired;
    vector<int> actual;
    int input;
    
    for(int i = 0; i < n; i++)
    {
        cin >> input;
        desired.push_back(input);
    }
    for(int i = 0; i < m; i++)
    {
        cin >> input;
        actual.push_back(input);
    }
    sort(desired.begin(), desired.end());
    sort(actual.begin(), actual.end());


}

到目前为止，我已经将 m、n 和 k 作为输入。然后，我获取所需的和实际的公寓尺寸，将它们分别放入所需和实际的向量中，并对它们进行排序。我不知道如何使用收集的数据来获得所需的输出:( 有什么建议吗？

Answer 1

首先，第一件事

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

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

• 因为它包含许多标准C++库头文件。虽然这对于在编程竞赛期间快速编写代码可能很方便，但不建议用于生产代码或项目或学习算法。

---

算法

• 我们这里不需要

  std::multiset<>

  。只需对两个变量（例如申请人、公寓）使用

  std::vector<>

  。

• 请注意，公寓和申请人的顺序并不重要，因此我们对它们进行排序。

• 我们迭代所有申请人并执行以下操作。

• 请注意，这就是我们“期望的”结果：

  if (j < m && apartments[j] <= applicants[i] + k)

  。每当这个条件满足时，我们就会增加结果 (

  res

  )。

• 如果

  apartments[j] < applicants[i] - k

  ，那么我们继续并仅增加 j 直到

  j < m

  ，这意味着我们访问了所有公寓。

在本地计算机上运行的代码

#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;
}

// You can test your function locally using a similar ifdef

#ifdef __APPLE__

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);
}

#endif

备注：

您可以定义一个main函数用于您自己的本地测试。例如，我使用：

#ifdef __APPLE__

int main()
{
   return 0;
}

#endif

---

对于不在本地运行（无论在其他地方）：

• 您将其更改为使用

  std::cin

  读取输入的主函数，类似于您所拥有的。

• 我们在 main 之外定义了一个函数，名为

  solve()

  来解决问题并返回结果 (

  res

  )。

int main()
{
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<int> A(n);
    std::vector<int> B(m);

    for (int i = 0; i < n; ++i)
    {
        std::cin >> A[i];
    }

    for (int i = 0; i < m; ++i)
    {
        std::cin >> B[i];
    }

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

}

---

在其他平台上运行的代码：

#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;
}

// This is for when you run it using `std::cin`:
int main()
{
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<int> A(n);
    std::vector<int> B(m);

    for (int i = 0; i < n; ++i)
    {
        std::cin >> A[i];
    }

    for (int i = 0; i < m; ++i)
    {
        std::cin >> B[i];
    }

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