[Atcoder] ABC302 :: D - Impartial Gift

A배열에 N개의 선물이 들어오고, B 배열에 M개의 선물이 들어온다고 한다. 
우리가 구하고 싶은 값은 A배열과 B배열에서 임의로 선물을 하나씩 선택했을때, abs(A - B) <= D인 선물을 찾고, 이중 가장 큰 합을 구하면 된다. 만약 없다면 -1을 출력하면 된다.

배열의 크기는 둘다 2e5이기 때문에 2중 for문은 힘들고 효율적으로 해결을 해야하는데, A를 기준으로 생각해보자. 
A라는 배열에 들어있는 어떤 a라는 값이 있을때, a가 정답의 후보가 되기 위해서는 B 배열에서 a-D보다 크고 a + D보다 작은 값들을 보면 된다. 그리고 우리는 이 경계에 있는 값만 확인하면 된다. abs(a - b)의 최댓값을 찾으면 되기 때문이다.

따라서 lower_bound와 upper_bound를 적절히 사용해서 경계에 있는 값을 찾은 후 이중 최댓값을 찾으면 된다. 그리고 이는 시간복잡도 O(NlogM)에 해결할 수 있다.

#include<iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#define NUM 200010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int n, m;
ll d;
vector<ll> A, B;

ll answer = -1;

int main() {
    cin >> n >> m >> d;
    for (int i=0; i<n; i++) {
        ll x;
        cin >> x;
        A.push_back(x);
    }
    for (int i=0; i<m; i++) {
        ll x;
        cin >> x;
        B.push_back(x);
    }
    
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    for (int i=0; i<A.size(); i++) {
        ll a = A[i];
        int idx = lower_bound(B.begin(), B.end(), a - d) - B.begin();
        if (abs(a - B[idx]) <= d) {
            answer = max(answer, a + B[idx]);
        }
        idx = upper_bound(B.begin(), B.end(), a + d) - B.begin();
        
        if (abs(a - B[idx-1]) <= d) {
            answer = max(answer, a + B[idx-1]);
        }
        
    }
    cout << answer << '\n';
}