8013 : 아파트
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$명의 아파트 신청자들과 $M$개의 아파트가 있습니다.
각 신청자 $i$는 자신이 선호하는 아파트 크기 $a_i$가 있으며, 크기 오차가 $K$ 이하인 아파트(즉, 크기가 $a_i - K$ 이상 $a_i + K$ 이하인 아파트)만 배정받을 수 있습니다.
각 아파트 $j$의 크기는 $b_j$입니다. 한 아파트에는 최대 한 명만 입주할 수 있으며, 한 신청자도 최대 하나의 아파트만 배정받을 수 있습니다.
최대한 많은 신청자들에게 아파트를 배정할 때, 배정 가능한 최대 신청자 수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N, M \le 2 \times 10^5$
• $0 \le K \le 10^9$
• $1 \le a_i, b_j \le 10^9$
각 신청자 $i$는 자신이 선호하는 아파트 크기 $a_i$가 있으며, 크기 오차가 $K$ 이하인 아파트(즉, 크기가 $a_i - K$ 이상 $a_i + K$ 이하인 아파트)만 배정받을 수 있습니다.
각 아파트 $j$의 크기는 $b_j$입니다. 한 아파트에는 최대 한 명만 입주할 수 있으며, 한 신청자도 최대 하나의 아파트만 배정받을 수 있습니다.
최대한 많은 신청자들에게 아파트를 배정할 때, 배정 가능한 최대 신청자 수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N, M \le 2 \times 10^5$
• $0 \le K \le 10^9$
• $1 \le a_i, b_j \le 10^9$
입력 설명
첫째 줄에 세 정수 $N, M, K$가 공백으로 구분되어 주어집니다.
둘째 줄에 각 신청자가 선호하는 크기 $a_1, a_2, \ldots, a_N$이 공백으로 구분되어 주어집니다.
셋째 줄에 각 아파트의 크기 $b_1, b_2, \ldots, b_M$이 공백으로 구분되어 주어집니다.
둘째 줄에 각 신청자가 선호하는 크기 $a_1, a_2, \ldots, a_N$이 공백으로 구분되어 주어집니다.
셋째 줄에 각 아파트의 크기 $b_1, b_2, \ldots, b_M$이 공백으로 구분되어 주어집니다.
출력 설명
아파트를 배정받을 수 있는 최대 신청자 수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 3 5
80 75 30 60
45 60 60
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
신청자의 희망 크기 배열 $a$와 아파트 크기 배열 $b$를 각각 오름차순으로 정렬합니다.
투 포인터(Two Pointers)를 사용하여 가장 작은 희망 크기를 가진 신청자부터 조건에 맞는 가장 작은 크기의 아파트를 그리디하게 매칭해 나갑니다.
투 포인터(Two Pointers)를 사용하여 가장 작은 희망 크기를 가진 신청자부터 조건에 맞는 가장 작은 크기의 아파트를 그리디하게 매칭해 나갑니다.