[백준 2110] 공유기 설치

홍시홍 2020. 2. 19. 21:34

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

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

www.acmicpc.net

요구사항

1. 공유기를 설치할수 있는 최대 거리 구하기

풀이

1. min~max에서 최대로 설정할 수 있는 거리를 정한다(이분 탐색)

2. 1에서 정한 dist가 가능한지 확인한다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll n, m;
ll map[200010];

bool check(ll nowdist) {
	ll now = map[0];
	int cnt = 1;
	
	for (int i = 1; i < n; i++) {
		if (map[i] - now >= nowdist) {
		//	cout << "A" << endl;
			cnt++;
			now = map[i];
		}
	}

	if (cnt >= m) 
		return true;
	return false;
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> map[i];
	}
	sort(map, map + n);
	ll low = 1;
	ll high = map[n-1] - map[0];
	ll ans = 0;
	while (low <= high) {
		ll mid = (low + high) / 2;
		//cout << "strat" << low << " " << high << endl;
		if (check(mid)) {
	//		cout << "A" << endl;
			low = mid + 1;
			ans = max(ans, mid);
		}
		else {
			high = mid - 1;
		}
		//cout << "end" << low << " " << high << endl;
	}
	cout << ans << endl;
}