我的代码的复杂性是什么?如何改进?

这是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";
}

在某些测试案例中,我超出了时间限制。

评论