44. 마구간 정하기 (이분검색 응용 : 결정 알고리즘) [정렬 & 이분탐색(결정알고리즘) & 투포인트 알고리즘 & 스택]

나의정답.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);

	int n, horseNum, i, j, tmp, rt, lt, mid, cnt = 1, idx;
	scanf("%d %d", &n, &horseNum);

	vector<int> a(n);

	// 마구간 번호 입력
	for (i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}

	// 마구간 번호 버블정렬
	for (i = 0; i < n; i++) {
		for (j = 0; j < n - i - 1; j++) {
			if (a[j] > a[j + 1]) {
				tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
			}
		}
	}

	lt = a[0];
	rt = a[n - 1];

	tmp = -1;
	while (lt <= rt) {
		mid = (lt + rt) / 2;
		idx = 0;
		cnt = 1;
		for (i = 1; i < n; i++) {
			if ( a[i] - a[idx] >= mid) {
				idx = i;
				cnt++;
			}
		}

		if ( cnt >= horseNum ) {
			lt = mid + 1;
			tmp = mid;
		}
		else {
			rt = mid - 1;
		}
	}
	printf("%d", tmp);
}