[C++] [CSES] Apartments (Sorting and Searching)

CSES Sorting and Searching 두번째 문제입니다.

아파트들의 넓이, 사람들이 원하는 넓이들을 입력으로 받습니다. 사람들은 아파트의 넓이와 자신들이 원하는 넓이와 차이가 얼마 나지 않으면 그 아파트를 선택합니다. 가장 많은 매칭이 일어나도록 하는 분배의 최댓값을 구하는 문제입니다.

그리디 문제는 정렬을 한다면 문제를 풀 수 있는 실마리가 생기는 경우가 많은 것 같습니다.

 

Task

 

There are n applicants and m free apartments. Your task is to distribute the apartments so that as many applicants as possible will get an apartment.

Each applicant has a desired apartment size, and they will accept any apartment whose size is close enough to the desired size.

Input

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.

Output

Print one integer: the number of applicants who will get an apartment.

Constraints

• 1≤n,m≤2⋅1e5
• 0≤k≤1e9
• 1≤ai,bi≤1e9

Example

Input:
4 3 5
60 45 80 60
30 60 75

Output:
2

 

Code

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

ll n, m, k, ans;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m >> k;
    vector<int> per(n), ap(m);
    for (int i=0;i<n;i++) cin >> per[i];
    for (int i=0;i<m;i++) cin >> ap[i];

    sort(per.begin(), per.end());
    sort(ap.begin(), ap.end());

    int pIdx = 0, aIdx = 0;
    while (pIdx < n && aIdx < m){
        ll up = per[pIdx] + k;
        ll dn = per[pIdx] - k < 0 ? 0 : per[pIdx] - k;

        if (dn<=ap[aIdx] && ap[aIdx]<=up){
            ans++;
            pIdx++;
            aIdx++;
        }
        else if (ap[aIdx]<dn){
            aIdx++;
        }
        else if (up<ap[aIdx]){
            pIdx++;
        }
    }
    cout << ans;
}

생각해야 하는 것

• 받은 두 아파트, 사람들 넓이 배열을 정렬합니다.
• 두 포인터 기법을 사용해서 작은 넓이부터 체크합니다.
• up, dn은 해당 사람이 받아들일 수 있는 최대 넓이와 최소 넓이입니다.
• 해당 아파트가 해당 사람의 조건에 맞는다면 리턴값, 두 인덱스를 1 올립니다.
• 아파트 넓이가 최소 넓이보다 작다면 아파트의 인덱스를 증가시킵니다. 왜냐하면 해당 사람의 조건에 맞는 집은 해당 아파트의 넓이보다 항상 커야하기 때문입니다.
• 아파트 넓이가 최대 넓이보다 크다면 사람의 인덱스를 증가시킵니다. 해당 아파트와는 무조건 더 큰 넓이를 원하는 사람만이 매칭될 수 있기 때문입니다.
• 사람이나 아파트의 인덱스가 배열의 끝에 온다면 while문을 종료시키고 ans값을 리턴합니다.