BOJ)8983 사냥꾼

문제: icpc.me/8983

KOI 2013 중,고등부 문제이다.

N마리의 동물들의 위치가 좌표로 주어지고 x축위에 M개의 사대가 존재하는데 이때 모든 사대의 사정거리는 공통적으로 L이다.

각 사대에서 동물들과의 거리는 [abs(x(동물)-x(사로))+y(동물)] 로 계산될 때 사냥 가능한 동물의 수를 출력하는 문제이다.

N과 M이 최대 10만까지 그리고 사정거리와 좌표는 1~ 1억까지 들어온다.

우리는 모든 사대와 각 동물들을 비교할 경우 O(N*M)의 시간 복잡도로 TLE를 보게 된다는 걸 알고 있다.

따라서 최대 NlogN의 알고리즘이 필요하다.

우리는 우선 동물들을 x좌표 기준으로 정렬 ,그리고 사대도 x좌표 기준으로 정렬을 할 것이다.

그 다음 동물들을 볼건데 어떤 동물 A를 사냥 가능한 사대는 여러개가 될 수 있지만 A를 기준으로 왼쪽에서 가장 가까운 사대와 오른쪽에서 가장 가까운 사대

이렇게 두 사대만 확인하면 나머지 사대는 확인하지 않아도 된다는 건 자명하다.

게다가 사대와 동물들을 x좌표 기준으로 정렬을 했으니 A동물을 확인 할때 Vn 사대와 Vn+1 사대를 확인했다면 A이후의 동물들을 확인 할 때도 Vn-1 이하의 사대들은 다시 볼일이 없다는 얘기가 된다.

이를 이용하여 사대와 동물들을 비교하여 답을 확인 할 경우 O(N+M)의 시간복잡도에 확인 가능하다.

전체 시간복잡도는 정렬을 하였기에 O(NlogN+MlogM)이 될 것이다.

#include <cstdio>
#include <algorithm>
#include <queue>
#define MAX_N 100000
using namespace std;
int xpos[MAX_N];
pair<int, int> a[MAX_N];
int m, n, l, xidx, res;
int cal(int x, int y, int z) {
    return abs(x - z) + y;
}
int main() {
    scanf("%d%d%d", &m, &n, &l);
    for (int i = 0; i < m; i++) {
        scanf("%d", &xpos[i]);
    }
    for (int i = 0; i < n; i++) 
        scanf("%d%d", &a[i].first, &a[i].second);
    sort(a, a + n);
    sort(xpos, xpos + m);
    for (int i = 0; i < n; i++) {
        while (xidx != m - 1 && xpos[xidx + 1] < a[i].first) {
            xidx++;
        }
        if (cal(a[i].first, a[i].second, xpos[xidx]) <= l) {
            res++;
            continue;
        }
        if (xidx != m - 1) {
            if (cal(a[i].first, a[i].second, xpos[xidx + 1]) <= l) {
                res++;
                continue;
            }
        }
    }
    printf("%d\n", res);
    return 0;
}