백준 8983번, 한국정보올림피아드(KOI) 2013 고등부 1번, 사냥꾼 풀이

문제

한국정보올림피아드 2013년 고등부 1번
백준 8983번

풀이

사대의 위치와 동물의 위치 간의 거리는 x좌표의 차이와 동물의 y좌표를 더한 값입니다. 또한, 사대는 x축 위에 있기 때문에 y좌표는 어느 사대를 선택하던 변하지 않습니다.

즉, 동물과 가장 가까운 사대를 구하려면 x좌표의 차이가 최소가 되는 사대를 찾으면 됩니다.

 

동물의 수와 사냥꾼의 수가 최대 100,000이므로 각 동물에 대한 최적의 위치에 있는 사대를 찾을 때 완전 탐색을 하면 TLE가 납니다.

 

가장 가까운 사대를 찾기 위해 동물의 x 좌표에 대한 이분 탐색을 해봅시다.
이 때, lower_bound를 사용하는 경우 사대의 후보가 2개가 나옵니다.

 

parametric search / lower_bound, 파라메트릭 서치

이 경우에는 lower_bound로 선택된 사대가 정답입니다.
하지만 아래의 경우에는 그렇지 않습니다.

parametric search / lower_bound [counter example], 파라메트릭 서치, 반례

즉, lower_bound로 선택된 값과 그 앞에 있는 값이 답의 후보가 될 수 있습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);

	vector<int> shooter;
	int m, n, l;
	cin >> m >> n >> l;
	while (m--) {
		int a;
		cin >> a;
		shooter.push_back(a);
	}

	sort(shooter.begin(), shooter.end());

	int ans = 0;
	while (n--) {
		int x, y;
		cin >> x >> y;

		auto ptr = min(shooter.end() - 1, lower_bound(shooter.begin(), shooter.end(), x));
		int right = *ptr, left = *(max(shooter.begin(), ptr - 1));

		int sel = right;
		if (right - x > x - left) sel = left;
		if (abs(sel - x) + y <= l) ans++;
	}

	cout << ans;
}