#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, c, a, lt, rt, mid, idx, answer = 0, count = 1;
scanf("%d %d", &n, &c);
vector<int> A(n+1, 0);
for(int i = 1; i < A.size(); i++)
{
scanf("%d", &a);
A[i] = a;
}
sort(A.begin(), A.end());
lt = 1;
rt = A[n];
while(lt <= rt)
{
mid = (lt + rt) / 2;
idx = 1;
for(int i = idx+1; i < A.size(); i++)
{
if(A[i] - A[idx] >= mid)
{
count++;
idx = i;
i = idx;
}
}
if(count < c)
{
rt = mid - 1;
count = 1;
}
else
{
lt = mid + 1;
if(answer == 0 || answer < mid)
answer = mid;
count = 1;
}
}
printf("%d", answer);
return 0;
}1. 마구간의 개수를 n, 말의 개수를 c 변수에 입력받고 마구간의 좌표를 변수 a에 입력받아 vector A에 추가한다.
lt, rt, mid 는 이분검색의 변수로 이용하고 idx는 탐색 시점, count는 마구간에 넣은 말의 수, answer는 최대거리이다.
먼저 vector A를 정렬한다.
| 1 | 2 | 4 | 8 | 9 |
lt와 rt는 양 끝점부터 시작한다. (lt = 1, rt = 9)
mid = (lt + rt) / 2 = (1 + 9) / 2 = 5
mid는 탐색거리를 나타낸다. 말을 최소한 거리가 5 차이날 때 마구간에 넣겠다는 의미이다.
| 1 | 2 | 4 | 8 | 9 |
1과 2의 거리는 1이기 때문에 말을 둘 수 없다.
| 1 | 2 | 4 | 8 | 9 |
1과 4의 거리도 3이기 때문에 말을 둘 수 없다.
| 1 | 2 | 4 | 8 | 9 |
1과 8의 거리는 7이기 때문에 말을 넣을 수 있고, 탐색을 8부터 다시 시작한다. count에 1을 더한다.(2)
| 1 | 2 | 4 | 8 | 9 |
8과 9의 거리는 1이기 때문에 말을 넣을 수 없다.
총 말을 넣은 횟수(count) = 2 이다. 총 말의 수인 c의 값 3보다 작기 때문에 거리를 5로 두었을 때는 말을 모두 넣을 수 없다. mid의 값을 줄여야하기 때문에 rt = mid - 1 = 5 - 1 = 4이 된다.
mid = (1 + 4) / 2 = 2
| 1 | 2 | 4 | 8 | 9 |
1과 2의 거리는 1이기 때문에 말을 둘 수 없다.
| 1 | 2 | 4 | 8 | 9 |
1과 4의 거리는 3이기 때문에 말을 넣을 수 있고, 탐색을 4부터 다시 시작한다. count에 1을 더한다.(2)
| 1 | 2 | 4 | 8 | 9 |
4와 8의 거리는 4이기 때문에 말을 넣을 수 있고, 탐색을 8부터 다시 시작한다. count에 1을 더한다.(3)
| 1 | 2 | 4 | 8 | 9 |
8과 9의 거리는 1이기 때문에 말을 넣을 수 없다.
총 말을 넣은 횟수(count) = 3 이다. 총 말의 수인 c의 값 3과 같기 때문에 거리를 2로 두었을 때는 말을 모두 넣을 수 있다. answer 는 초기에 0이었기 때문에 2가 된다. mid의 값을 키워서 가능한 수가 있는지 확인하기 위해 lt = mid + 1 = 1 + 1 = 2이 된다.
mid = (2 + 4) / 2 = 3
| 1 | 2 | 4 | 8 | 9 |
1과 2의 거리는 1이기 때문에 말을 둘 수 없다.
| 1 | 2 | 4 | 8 | 9 |
1과 4의 거리는 3이기 때문에 말을 넣을 수 있고, 탐색을 4부터 다시 시작한다. count에 1을 더한다.(2)
| 1 | 2 | 4 | 8 | 9 |
4와 8의 거리는 4이기 때문에 말을 넣을 수 있고, 탐색을 8부터 다시 시작한다. count에 1을 더한다.(3)
| 1 | 2 | 4 | 8 | 9 |
8과 9의 거리는 1이기 때문에 말을 넣을 수 없다.
총 말을 넣은 횟수(count) = 3 이다. 총 말의 수인 c의 값 3과 같기 때문에 거리를 3으로 두었을 때는 말을 모두 넣을 수 있다. answer는 2, 거리는 3이기 때문에 3이 된다. 이후는 lt가 rt와 같아지기 때문에 while문이 break 된다.
