Split Array Largest Sum

Problem (yeniden ifade)

nums dizisini m boş olmayan bitişik alt diziye böl. Amaç, alt dizi toplamlarının en büyüğünü olabildiğince küçük tutmak; o en büyük toplamın minimumunu döndür.

Sezgi

Uygulanabilirlik izin verilen maks toplamda monotoniktir. Cevabı ikili ara.

Yaklaşımlar

export function splitArray(nums: number[], m: number): number {
  let lo = Math.max(...nums), hi = nums.reduce((a, b) => a + b, 0);
  const ok = (cap: number) => {
    let pieces = 1, load = 0;
    for (const x of nums) {
      if (load + x > cap) { pieces++; load = 0; }
      load += x;
    }
    return pieces <= m;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (ok(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}

export function splitArray(nums: number[], m: number): number {
  let lo = Math.max(...nums), hi = nums.reduce((a, b) => a + b, 0);
  const ok = (cap: number) => {
    let pieces = 1, load = 0;
    for (const x of nums) {
      if (load + x > cap) { pieces++; load = 0; }
      load += x;
    }
    return pieces <= m;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (ok(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}

Şablon bağlantısı

Maksimum yüke binary search; greedy bölme sayısı fizibilite kontrolü.

Yansıma

• “En büyük parçanın toplamını küçült” monotonik: kapasite artınca m parça yetmeye başlar. lo = max(nums) neden?
• feasible(cap) bir geçişte parça sayar. m’den fazla parça = çok küçük cap.
• m = 1 (tüm dizi) ve m = n (her eleman bir parça) uçları.