BOJ 11973 - Angry Cows (usaco silver, 이분탐색)

 

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

 

딱 봐도 이분탐색.

 

구현하는걸 까먹어서 옛날 코드 참고해서 풀었다.

 

폭발반지름R 대신 폭발구간 R'에 대해 이분탐색하였다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int n,k,arr[50000];
/* 처음 짠 논리. 밑에서 간략화 했다.
bool isPossible(int m) {
	int i = 0, cnt = 0;;
	while(cnt<k) {
		int t = arr[i];
		int last = upper_bound(arr, arr + n, t + m) - arr;
		i = last;
		cnt++;
		if (i >= n) break;
	}
	return i >= n ? true : false;
}
*/

bool isPossible(int m) {
	int i = 0, cnt = 0;
	while(cnt<k && i<n) {
		i = upper_bound(arr, arr + n, arr[i] + m) - arr;
		cnt++;
	}
	return i == n ? true : false;
}

int main() {
	cin >> n >> k;
	
	for (int i = 0; i < n; i++) cin >> arr[i];
	sort(arr, arr + n);

	int lo = 1, hi = arr[n-1];
	while (lo < hi) {
		int mid = (lo + hi) / 2;

		bool flag = isPossible(mid);
		if (flag) hi = mid;
		else lo = mid + 1;
	}
	cout << (lo%2 ? lo/2+1 : lo/2) << '\n';
}

arr에 부술 것들의 좌표를 저장하고 sort해준다

 

R'은 1~arr[n-1]까지의 값을 가질 수 있다. (lo = 1, hi = arr[n-1]이 초기값)

 

이분탐색 while문의 mid가 탐색 대상인데, R'이 mid일때 조건을 만족하는지 반환하는 isPossible함수가 다소 조잡하다.(O(10logn))

 

int lo = -1, hi = A[N-1];
	while(lo+1 < hi){
		unsigned int mid = (lo+hi)/2, pos = 0;
		for(int i = 0; i < K && pos < N; ++i)
			pos = upper_bound(A, A+N, A[pos]+mid*2) - A;
		(pos == N ? hi : lo) = mid;
	}
printf("%d\n", hi);

kks227님의 코드.

얼추 논리는 비슷한 것 같다.