[Algorithm] C++ 마구간 정하기(이분검색)

입력설명

첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다. 둘째 줄부터 N개의 줄에 걸쳐 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 한 줄에 하나씩 주어집니다.

출력설명

첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.

 

입력예제

5 3 

1 2 8 4 9

 

출력예제

3

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>

using namespace std;
int n;
int Count(int len, int x[]) {
	int i, cnt = 1, pos = x[1];
	for (i = 2; i <= n; i++) {
		if (x[i] - pos >= len) {
			cnt++;
			pos = x[i];
		}
	}
	return cnt;
}
int main() {
	int m, i, lt = 1, rt, mid, res;
	scanf("%d %d", &n, &m);
	int* x = new int[n + 1]; // 동적 배열로 선언 , 200000을 선언하기엔 너무 크기 때문!
	for (i = 1; i <= n; i++) {
		scanf("%d", &x[i]);
	}
	sort(x + 1, x + n + 1);
	rt = x[n];
	while (lt <= rt) {
		mid = (lt + rt) / 2;
		if (Count(mid, x) >= m) {
			res = mid;
			lt = mid + 1;
		}
		else rt = mid - 1;
	}
	printf("%d\n", res);
	return 0;
}