Minimize Max Distance to Gas Station

Problem (yeniden ifade)

Sayı doğrusuna (sıralı istasyonlar) k yeni benzin istasyonu ekle. Komşu istasyonlar arasındaki maksimum mesafeyi en aza indir.

Sezgi

Maks boşluk D, ≤k ekleme ile mümkünse daha büyük D de mümkündür. Gerçel değerli D üzerinde ikili arama.

Yaklaşımlar

export function minmaxGasDist(stations: number[], k: number): number {
  let lo = 0, hi = stations[stations.length - 1]! - stations[0]!;
  const ok = (d: number) => {
    let need = 0;
    for (let i = 1; i < stations.length; i++) {
      const gap = stations[i]! - stations[i - 1]!;
      need += Math.ceil(gap / d) - 1;
    }
    return need <= k;
  };
  for (let t = 0; t < 80; t++) {
    const mid = (lo + hi) / 2;
    if (ok(mid)) hi = mid; else lo = mid;
  }
  return hi;
}

export function minmaxGasDist(stations: number[], k: number): number {
  let lo = 0, hi = stations[stations.length - 1]! - stations[0]!;
  const ok = (d: number) => {
    let need = 0;
    for (let i = 1; i < stations.length; i++) {
      const gap = stations[i]! - stations[i - 1]!;
      need += Math.ceil(gap / d) - 1;
    }
    return need <= k;
  };
  for (let t = 0; t < 80; t++) {
    const mid = (lo + hi) / 2;
    if (ok(mid)) hi = mid; else lo = mid;
  }
  return hi;
}

Şablon bağlantısı

Maks komşu boşluğa binary search; greedy istasyon sayısı fizibilite kontrolü.

Yansıma

• Cevap bir gerçek sayı (maksimum komşu mesafe). feasible(d) k istasyonun d’yi aşan boşluklara yetip yetmediği.
• Kayan nokta: hi-lo > eps döngüsü. eps çok kaba olursa cevap kabul bandını kaçırır.
• k = 0: cevap mevcut max boşluk.