백준 8983번 사냥꾼 [C++]

https://www.acmicpc.net/problem/8983

 

 

#문제 간단 정리

 

#문제 해결 방법

 

우선 동물의 개수가 10만개

사대의 개수가 10만개

 

즉 완전 탐색으로는 10만 * 10만 으로 100억이라 

완전 시간초과

그래프 탐색도 최악의 경우에는 완전탐색이기에 방법이 없다

 

dp 는 딱히 떠올리는게 없고

 

결국 동물의 위치와 가장 가까운 사대는 x가 가까울수록 위치도 무조건 가까워지니

이분탐색 log n으로 풀어주면 된다.

 

사대정렬 n log n  + m log n 

으로 시간복잡도가 충분하니 이대로 풀면 된다.

 

 

#전체 코드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

vector<pair<ll, ll>> animals;
vector<ll> shooters;

int n, m;
ll l;

bool isReach(ll shooter , ll ax , ll ay) {
    ll a = abs(ax - shooter) + ay;

    if (a <= l) {
        return true;
    }
    else {
        return false;
    }
}

bool bs(ll ax, ll ay) {

    ll l = 1;
    ll r = m;

    while (l <= r) {
        ll mid = (l + r) / 2;

        if (isReach(shooters[mid], ax, ay))
            return true;

        if (shooters[mid] >= ax) {
            r = mid -1;
        }
        else if (shooters[mid] < ax) {
            l = mid + 1;
        }

    }

    return false;

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n >> l;

    animals.resize(n+1);
    shooters.resize(m+1);


    for (int i = 1; i <= m; i++) {
        cin >> shooters[i];
        
    }
    sort(shooters.begin(), shooters.end());

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        cin >> animals[i].first >> animals[i].second;

        if (bs(animals[i].first, animals[i].second)) ans++;
    }

    cout << ans << '\n';

    return 0;
}