Book Allocation Problem

Q: Kitap Dağıtımı Problemi, En Büyük Dizi Toplamını Bölme Problemi ile aynı mıdır?

Evet. Her ikisi de bir diziyi sabit sayıda boş olmayan bitişik bloğa böler ve en büyük blok toplamını en aza indirir; aynı ikili arama ve aynı açgözlü kontrol her ikisini de çözer. Kitap sürümünde -1 durumu da eklenir.

Q: Kitap Tahsis Problemi'nin zaman karmaşıklığı nedir?

O(n log S) zaman ve O(1) ek alan; burada n kitap sayısı, S ise toplam sayfa sayısıdır. Denenen her sınır, kitaplar üzerinde bir geçiş gerektirir ve arama yaklaşık log2 S sınır dener: 5 × 10^8 sayfalık bir rafta 29.

Q: Kitapları tahsis etmek ne zaman imkânsızdır?

Yalnızca öğrenci sayısı kitap sayısından fazlaysa; çünkü her öğrencinin en az bir kitaba ihtiyacı vardır. Yeterli sayıda kitap varsa, iki veya daha fazla kitaptan oluşan herhangi bir grup, herkesin bir kitabı olana kadar son kitabını hiç kitabı olmayan bir öğrenciye verebilir.

Ortaİkili arama Açgözlü

+10

Bir raftaki kitaplar sabit bir sırada durur ve pages[i], i numaralı kitaptaki sayfa sayısını belirtir. Kitapları students öğrenci arasında paylaştır: her öğrenci, yan yana duran kitaplardan oluşan kesintisiz bir grup almalı, herkes en az bir kitap almalı ve her kitap tam olarak bir öğrenciye verilmelidir. Bir öğrencinin yükü, aldığı toplam sayfa sayısıdır.

En ağır yükün mümkün olan en küçük değerini döndür. Öğrenci sayısı kitap sayısından fazlaysa -1 döndür.

Fonksiyon

allocateBooks(pages: integer-array, students: integer) → integer

pagesinteger-array: Raf sırasına göre her kitabın sayfa sayısı
studentsinteger: kitapları paylaşan öğrenci sayısı
Döndürürinteger: mümkün olan en küçük en ağır yük veya öğrenci sayısı kitap sayısından fazlaysa -1

Kısıtlar

1 ≤ pages.length ≤ 5000
1 ≤ pages[i] ≤ 10⁵
1 ≤ students ≤ 10⁴
-1 döndürün; students > pages.length olduğunda.

Örnekler

Girdi: pages = [25, 40, 15, 30, 50]students = 3
Çıktı: 65
Açıklama: [25, 40], [15, 30] ve [50] dağıt: yükler 65, 45 ve 50. 64'lük bir sınır başarısız olur: dağıtımda [25], [40, 15], [30], [50] olur; dört öğrenci.

Girdi: pages = [10, 20]students = 3
Çıktı: -1
Açıklama: İki kitap, üç öğrenciye birer kitap vermeye yetmez, bu yüzden cevap -1.

Ek soru

Yukarı yuvarlanmış ortalama payın en kalın kitapla toplamının her zaman geçerli bir sınır olduğunu kanıtlayın. İnce kitaplardan oluşan bir rafta bu üst sınır kaç kontrol kazandırır?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Rafı kesmenin çok fazla yolu var, ancak tek bir sayfa sınırını denemek kolaydır: kitapları raf sırasına göre dağıtın, bir kitap sınırı aşacaksa sonraki öğrenciye geçin ve öğrenci sayısını sayın. Daha yüksek bir sınır hiçbir zaman daha fazla öğrenci gerektirmez; bu yüzden işe yarayan sınırlar tek bir aralık oluşturur ve ikili arama bu aralığın nerede başladığını bulur.

Sayfa sınırını her seferinde bir sayfa artırın

Doğru, ama en büyük testlerde bitmiyor

Sezgi

L = max(pages) değerinden başla; çünkü birisi en kalın kitabı taşıyor. Açgözlü sayım students içine sığana kadar L değerini her seferinde bir sayfa artır. Daha düşük tüm sınırlar başarısız olduğundan, sığan ilk sınır cevaptır. İlk örnekte 50 ile 64 arasındaki her sınır dört öğrenci gerektirir, 65 ise üç öğrenci gerektirir: 16 kontrol.

Cevap tüm raf olabilir: bir öğrenci ve 10^5 sayfalık 5000 kitap, yaklaşık 5 × 10^8 sınır anlamına gelir; her biri 5000 kitabın üzerinden bir geçiştir. Süre sütununda A cevap, m ise en kalın kitaptır.

Algoritma

students > pages.length ise -1 döndür.
L sınırı için açgözlü sayımı yaz: bir öğrenciyle ve 0 yükle başla; load + pages[i] > L olduğunda bir öğrenci ekle ve yükü pages[i] olarak ayarla, aksi hâlde kitabı yüke ekle.
L değerini en kalın kitabın sayfa sayısına ayarla.
L için sayım students değerinden fazlayken L değerine 1 ekle.
L değerini döndür.

def studentsNeeded(pages, limit):
    count, load = 1, 0  # the first student starts with no pages
    for p in pages:
        if load + p > limit:
            count += 1  # this book opens the next student's block
            load = p
        else:
            load += p
    return count


def allocateBooks(pages, students):
    if students > len(pages):
        return -1  # someone would get no book
    limit = max(pages)  # the thickest book has to fit somewhere
    while studentsNeeded(pages, limit) > students:
        limit += 1
    return limit

Sayfa sınırında ikili arama

Sezgi

Açgözlü sayım, L sınırı altında herhangi bir paylaşımın kullanabileceği en az öğrenci sayısıdır. Öğrencileri tek tek başka herhangi bir paylaşımla karşılaştırdığımızda, açgözlü paylaşımda her öğrenci yalnızca sıradaki kitap sığmadığında durur; bu nedenle rafta en az diğer paylaşım kadar ilerler. Elinizdekinden daha az öğrenci olması sorun değildir: iki kitap tutan bir öğrenci, kitap tutmayan bir öğrenciye bir kitabı verebilir ve hiçbir öğrencinin yükü artmaz.

Dolayısıyla L, açgözlü sayım en fazla students olduğunda işe yarar. L sınırında işe yarayan her şey L+1 sınırında da işe yarar; bu nedenle ikili arama işe yarayan ilk sınırı bulur.

Aralık, en ağır yük her ikisinden de en az bu kadar olduğu için, max(pages) ile ortalama payın (yukarı yuvarlanmış total / students) büyük olanından başlar. Üst sınır total değeridir. İlk örnekte aralık 54 ile 160 arasındadır ve arama 107, 80, 67, 60, 64, 66 ve 65 değerlerini dener.

Algoritma

students > pages.length ise -1 döndür.
total değerini topla ve en kalın kitabı bul. lo değerini en kalın kitap ile (total + students - 1) / students değerinden büyük olanına, hi = total olarak ayarla.
lo < hi olduğu sürece mid = lo + (hi - lo) / 2 değerini al.
mid için açgözlü sayımı çalıştır. Sonuç en fazla students ise hi = mid olarak ayarla; değilse lo = mid + 1 olarak ayarla.
lo değerini döndür.

def studentsNeeded(pages, limit):
    count, load = 1, 0  # the first student starts with no pages
    for p in pages:
        if load + p > limit:
            count += 1  # this book opens the next student's block
            load = p
        else:
            load += p
    return count


def allocateBooks(pages, students):
    if students > len(pages):
        return -1  # someone would get no book
    total = sum(pages)
    # no limit can be below the thickest book or below the average share
    lo = max(max(pages), (total + students - 1) // students)
    hi = total  # one student could carry the whole shelf
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if studentsNeeded(pages, mid) <= students:
            hi = mid  # mid is enough, so the answer is mid or lower
        else:
            lo = mid + 1  # mid needs too many students
    return lo

Tuzaklar ve uç durumlar

-1 kontrolünü atlamak. [10, 20] ve 3 öğrenci için, 20 sınırında greedy sayısı 2 olur; bu nedenle arama 20 döndürür.
Aralığı yalnızca ortalama payla başlatmak. [1, 9] ve 2 öğrenci için ortalama 5'tir; bu durumda greedy, 9 sayfalı kitabı tek başına verir, 2 sayar ve 5 döndürür.
Tam olarak students değerini test etmek. [5, 5, 5, 5, 5, 5] ve 4 öğrenci için yanıt 10'dur; greedy sayısı ise 3'tür.
Kitapları sıralamak. 2 öğrenciyle [10, 1, 1, 10] sonucu 11 verir; ancak [1, 1, 10, 10] olarak sıralandığında 12 verir.

Sıkça sorulan sorular3

Kitap Dağıtımı Problemi, En Büyük Dizi Toplamını Bölme Problemi ile aynı mıdır?

Evet. Her ikisi de bir diziyi sabit sayıda boş olmayan bitişik bloğa böler ve en büyük blok toplamını en aza indirir; aynı ikili arama ve aynı açgözlü kontrol her ikisini de çözer. Kitap sürümünde -1 durumu da eklenir.

Kitap Tahsis Problemi'nin zaman karmaşıklığı nedir?

O(n log S) zaman ve O(1) ek alan; burada n kitap sayısı, S ise toplam sayfa sayısıdır. Denenen her sınır, kitaplar üzerinde bir geçiş gerektirir ve arama yaklaşık log2 S sınır dener: 5 × 10^8 sayfalık bir rafta 29.

Kitapları tahsis etmek ne zaman imkânsızdır?

Yalnızca öğrenci sayısı kitap sayısından fazlaysa; çünkü her öğrencinin en az bir kitaba ihtiyacı vardır. Yeterli sayıda kitap varsa, iki veya daha fazla kitaptan oluşan herhangi bir grup, herkesin bir kitabı olana kadar son kitabını hiç kitabı olmayan bir öğrenciye verebilir.

def allocateBooks(pages, students):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

pages = [25, 40, 15, 30, 50]
students = 3

Beklenen Çıktı