[백준 2110] 공유기 설치

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

2110번: 공유기 설치

요구사항

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;
}