Căn hộ (sắp xếp và tìm kiếm)
Xem dạng PDFCó ~n~ người nộp đơn và ~m~ căn hộ trống. Nhiệm vụ của bạn là phân phối các căn hộ sao cho càng nhiều người nộp đơn càng tốt nhận được một căn hộ.
Mỗi người nộp đơn có kích thước căn hộ mong muốn, và họ sẽ chấp nhận bất kỳ căn hộ nào có kích thước đủ gần với kích thước mong muốn.
Đầu vào:
Dòng đầu tiên chứa ba số nguyên ~n, m, k~:
~n~: số người nộp đơn
~m~: số căn hộ
~k~: độ lệch cho phép tối đa giữa kích thước căn hộ mong muốn và kích thước thực tế
Dòng tiếp theo chứa ~n~ số nguyên ~a₁, a₂, ..., aₙ~: kích thước căn hộ mong muốn của mỗi người nộp đơn.
Một người có mong muốn là ~x~ sẽ chấp nhận căn hộ có kích thước từ ~x - k~ đến ~x + k~.
Dòng cuối chứa m số nguyên ~b₁, b₂, ..., bₘ~: kích thước của các căn hộ.
Đầu ra: In ra một số nguyên: số lượng người nộp đơn nhận được căn hộ
Ràng buộc:
~1 \le n, m \le 2 \cdot 10^5~
~0 \le k \le 10^9~
~1 \le a_i, b_i \le 10^9~
Ví dụ :
Input:
4 3 5
60 45 80 60
30 60 75
Output:
2
Bình luận
include <bits/stdc++.h>
using namespace std; long long n,m,k; int main() { ios::syncwithstdio(false); cin.tie(nullptr); cin >> n >> m >> k; vector<int> a(n), b(m); for (int i = 0; i < n; i++) cin >> a[i]; for (int j = 0; j < m; j++) cin >> b[j]; sort(a.begin(), a.end()); sort(b.begin(), b.end()); int i = 0, j = 0, ans = 0; while (i < n && j < m) { if (b[j] < a[i] - k) { j++; } else if (b[j] > a[i] + k) { i++; } else { ans++; i++; j++; } }
}