공부공간

BOJ - 8983 ) 사냥꾼 본문

알고리즘/이분탐색

BOJ - 8983 ) 사냥꾼

개발자가될수있을까? 2020. 10. 1. 00:19


www.acmicpc.net/problem/8983

 

8983번: 사냥꾼

입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌

www.acmicpc.net


사냥꾼의 사정거리를 계산할 때에, 동물에서 가장가짜운 사대의 왼쪽 오른쪽만 보면된다. 전체탐색 x

 

이분탐색으로 사대의 위치를 찾고, 정확히 찾는다면 L값이 Y값보다 같거나 큰지의 여부를 파악하고,

 

찾지못했다면, 양옆의 사대의 X값의 차이 + y 값이 L사정거리보다 같거나 작으면 범위안에 있는 것이다.

 


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int m = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
		int l = Integer.parseInt(st.nextToken());
		int []mm = new int[m];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<m;i++) mm[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(mm);
		int answer = 0;
		for(int i=0; i<n;i++) {
			st = new StringTokenizer(br.readLine());
			int x=  Integer.parseInt(st.nextToken());
			int y=  Integer.parseInt(st.nextToken());
			if(x <=mm[0]) {
				if(l-((mm[0]-x)+y) >=0) {
					answer++;
				}
			} else if(x>=mm[m-1]) {
				if(l-((x-mm[m-1])+y) >=0) {
					answer++;
				}
			} else {
				int s = 0;
				int e = m-1;
				while(s<e) {
					int mid = (s+e)>>1;
					if(mm[mid]==x) {
						if(l-y >=0) {
							answer++;
						}
						break;
					} else if(mm[mid] < x) {
						s = mid;
					} else {
						e = mid;
					}
					
					if(s+1==e && mm[s]<x && mm[e]>x) {
						if(l-(x-mm[s]+y) >= 0) {
							answer++;
							break;
						}
						if(l-(mm[e]-x+y) >= 0) {
							answer++;
							break;
						}
						break;
					}
				}
			}
		}
		System.out.println(answer);
	}
}

'알고리즘 > 이분탐색' 카테고리의 다른 글

BOJ - 2473 ) 세용액  (0) 2020.08.28
BOJ - 2110 ) 공유기 설치  (0) 2019.12.17
BOJ - 2805 ) 나무자르기  (0) 2019.12.17
BOJ - 2512 ) 예산  (0) 2019.12.16
Comments