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

Mediumbinary-search-on-answer

Capacity To Ship Packages Within D Days

Problem (yeniden ifade)

Paketler sırayla days gün içinde sevk edilmeli. Bunu mümkün kılan en küçük gemi ağırlık kapasitesini bul.

Sezgi

Uygulanabilirlik kapasitede monotonik: C işe yarıyorsa C+1 de yarıyor. Kapasite üzerinde ikili arama yap.

Yaklaşımlar

Kapasite üzerinde ikili arama

Tested only

Time O(n log S)Space O(1)

Fikir. lo = max(weights), hi = sum(weights). mid kapasite için greedy olarak gereken gün sayısını say.

Adım adım. weights=[1,2,3,4,5,6,7,8,9,10], days=5 → cevap 15.

Trade-off’lar. Koko ile aynı kalıp; net bir canShip(cap) yüklemi tanımla.

Solution

export function shipWithinDays(weights: number[], days: number): number {
  let lo = Math.max(...weights);
  let hi = weights.reduce((a, b) => a + b, 0);
  const ok = (cap: number) => {
    let d = 1, load = 0;
    for (const w of weights) {
      if (load + w > cap) { d++; load = 0; }
      load += w;
    }
    return d <= days;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (ok(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

export function shipWithinDays(weights: number[], days: number): number {
  let lo = Math.max(...weights);
  let hi = weights.reduce((a, b) => a + b, 0);
  const ok = (cap: number) => {
    let d = 1, load = 0;
    for (const w of weights) {
      if (load + w > cap) { d++; load = 0; }
      load += w;
    }
    return d <= days;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (ok(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Yansıma

90 saniyeden kısa sürede bu kalıbı seçtiren ipucu neydi?
Yanlış değişmezi hangi girdi bozar?