Stable Setup (Decision Algorithm)
03 Aug, 2021Problem
N stables are on a vertical line. Each stable has the coordinates of x1, x2, x3, …, xN, and there is no overlap of coordinates between the stables.
Hyeonsu has C horses, who don’t like being close to each other.
Each stable can only hold one horse, and we want the horses to be placed in the stable so that the distance between the two closest horses is maximized.
Write a program that outputs the maximum value that maximizes the distance between the two closest horses when C horses are placed in N stables.
input
- On the first line, the natural numbers N(3<=N<=200,000) and C(2<=C<=N) are given with a space between them
- The second line gives the stable coordinates xi (0<=xi<=1,000,000,000) in turn
5 3
1 2 8 4 9output
Print the maximum distance of the two closest horses in the first line.
3;Solution
Desision Algorithm
function count(stable, dist) {
let cnt = 1,
ep = stable[0];
for (let i = 1; i < stable.length; i++) {
if (stable[i] - ep >= dist) {
cnt++;
ep = stable[i];
}
}
return cnt;
}
function solution(c, stable) {
let answer;
stable.sort((a, b) => a - b);
let lt = 1,
rt = stable[stable.length - 1];
while (lt <= rt) {
let mid = parseInt((lt + rt) / 2);
if (count(stable, mid) >= c) {
answer = mid;
lt = mid + 1;
} else rt = mid - 1;
}
return answer;
}using sort()
function solution(c, stable) {
let answer;
stable.sort((a, b) => a - b);
let sp = stable.shift(),
ep = stable.pop(),
mid = parseInt((sp + ep) / 2),
distArr = [];
for (let x of stable) distArr.push([x, Math.abs(mid - x)]);
// sort close to mid
distArr.sort(([p1, dist1], [p2, dist2]) => dist1 - dist2);
// possible stable by horse count
let avaliable = distArr.slice(0, c - 2),
// last one is the worst case, the farthest from mid
worstPos = avaliable[avaliable.length - 1][0];
// minimum distance
answer = Math.min(Math.abs(sp - worstPos), Math.abs(ep - worstPos));
return answer;
}