Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

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

Maks boşlukta ikili arama

Tested only

Time O(n log(1/ε))Space O(1)

Fikir. mid D için a,b arasına gereken istasyon ceil((b-a)/D)-1; toplam ≤ k.

Adım adım. stations=[1,2,3,4,5,6,7,8,9,10], k=9 → cevap 0.5.

Trade-off’lar. Kayan noktalı ikili aramada epsilon gerekir; heap simülasyonu ayrık alternatiftir.

Solution

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;
}

Yansıma

90 saniyenin altında hangi ipucu bu kalıbı seçtirdi?
Hangi girdi yanlış bir değişmezi bozar?