백준 BOJ 8983 - 사냥꾼

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

8983번: 사냥꾼

KOI 2013 중고등부 1번

사대에서 맞출수 있는 동물을 매칭하면 O(NM)으로 시간초과를 받는다.

각 동물들에서 가장 가까운 사대를 O(lgM) 으로 매칭하고 이를 O(N)번 반복해서

전체 시간복잡도가 O(NlgM)이 되게하는게 정석적인 풀이

 

가장 가까운 사대를 O(lgM) 에 매칭하는데 있어서,

이분탐색을 사용해야 한다.

V에서 K 이상의 수를 찾아 해당 위치의 iter 값을 반환하는 lower_bound 내장함수를

이분탐색에 사용하였다.

직접 구현하는 습관좀 들여야하는데 ㅠㅠ

 lower_bound(V.begin(), V.end(), K);

lower_bound로 매칭된 위치가 제일 첫 값인 경우,

왼쪽 사로가 없을 수 있고,

정 반대로 제일 뒷 값인 경우, 오른쪽 사로가 없을 수 있다.

이에 유의하면서 소스코드를 작성해주도록 한다.

 

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

vector<int> v;
int N,M,X;

int main(){
	int a,b;
	cin >> M >> N >> X;
	for(int i=0; i<M; i++){
		cin >> a;
		v.push_back(a);
	}
	
	sort(v.begin(), v.end());
	int ans = 0;
	
	for(int i=0; i<N; i++){
		cin >> a >> b;
		
		
		int val = 998244353;
		int idx = lower_bound(v.begin(), v.end(), a)-v.begin();
		if(idx != 0) val = min(val, abs(v[idx-1]-a) + b);
		if(idx != M) val = min(val, abs(v[idx]-a) + b);
		
		if(val <= X) ans++;
	}
	
	cout << ans;
	return 0;
}