这是CSES问题集中的问题。
有n个申请人和m个免费公寓。您的任务是分发公寓,以便有尽可能多的申请人获得公寓。
每个申请人都有所需的公寓大小,并且他们将接受任何尺寸足够接近所需大小的公寓。
输入项
The first input line has three integers n, m, and k: the number of applicants, the number of apartments, and the maximum allowed difference.
The next line contains n integers a1,a2,…,an: the desired apartment size of each applicant. If the desired size of an applicant is x, he or she will accept any apartment whose size is between x−k and x+k.
The last line contains m integers b1,b2,…,bm: the size of each apartment.
输出
Print one integer: the number of applicants who will get an apartment.
约束条件
1 ≤ n, m ≤ 2e5
0 ≤ k ≤ 1e9
1 ≤ ai, bi ≤ 1e9
我的尝试
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <utility>
typedef long long int ll;
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m, k;
cin >> n >> m >> k;
vector<int> vn, vm;
for (int i = 0; i < n; i++)
{
int p;
cin >> p;
vn.push_back(p);
}
for (int i = 0; i < m; i++)
{
int p;
cin >> p;
vm.push_back(p);
}
int c = 0;
sort(vn.begin(), vn.end());
sort(vm.begin(), vm.end());
for (int i = 0; i < m; i++)
{
for (int j = 0; j < vn.size(); j++)
{
if (vm[i] <= vn[j] + k && vm[i] >= vn[j] - k)
{
c++;
vn.erase(vn.begin() + j);
break;
}
if (vn[j] < vm[i] - k)
{
vn.erase(vn.begin() + j);
j--;
continue;
}
if (vn[j] > vm[i] + k)
{
break;
}
}
}
cout << c << "\n";
}
在某些测试案例中,我超出了时间限制。