Book Allocation Problem

Q: Apakah Book Allocation Problem sama dengan Split Array Largest Sum?

Ya. Keduanya membagi array menjadi sejumlah blok berurutan yang tidak kosong dan jumlahnya tetap, lalu meminimalkan jumlah terbesar dari sebuah blok. Pencarian biner yang sama dengan pemeriksaan greedy yang sama dapat menyelesaikan keduanya. Versi buku menambahkan kasus -1 .

Q: Berapa kompleksitas waktu Masalah Alokasi Buku?

Waktu O(n log S) dan ruang ekstra O(1) , dengan n sebagai jumlah buku dan S sebagai total jumlah halaman. Setiap batas yang dicoba memerlukan satu kali penelusuran semua buku, dan pencarian mencoba sekitar log2 S batas: 29 untuk rak dengan 5 × 10^8 halaman.

Q: Kapan buku-buku tidak mungkin dialokasikan?

Hanya jika jumlah siswa lebih banyak daripada jumlah buku, karena setiap siswa membutuhkan setidaknya satu buku. Jika jumlah buku mencukupi, setiap tumpukan yang terdiri dari dua buku atau lebih dapat memberikan buku terakhirnya kepada siswa yang belum memiliki buku, sampai semua siswa memiliki satu buku.

SedangBinary search Greedy

+10

Sebuah rak menyimpan buku dalam urutan tetap, dan pages[i] adalah jumlah halaman dalam buku i. Bagikan buku-buku tersebut kepada students siswa: setiap siswa mendapat satu rangkaian buku berdekatan yang tidak terputus, minimal satu buku untuk setiap siswa, dan setiap buku diberikan tepat kepada satu siswa. Beban seorang siswa adalah total jumlah halaman yang mereka terima.

Kembalikan nilai terkecil yang mungkin untuk beban terberat. Jika jumlah siswa lebih banyak daripada jumlah buku, kembalikan -1.

Fungsi

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

pagesinteger-array: jumlah halaman setiap buku, sesuai urutan di rak
studentsinteger: jumlah siswa yang berbagi buku
Mengembalikaninteger: beban terberat sekecil mungkin, atau -1 jika jumlah siswa lebih banyak daripada jumlah buku

Batasan

1 ≤ pages.length ≤ 5000
1 ≤ pages[i] ≤ 10⁵
1 ≤ students ≤ 10⁴
Kembalikan -1 saat students > pages.length.

Contoh

Input: pages = [25, 40, 15, 30, 50]students = 3
Output: 65
Penjelasan: Bagikan [25, 40], [15, 30], dan [50]: muatannya 65, 45, dan 50. Batas 64 tidak berhasil: pembagian menghasilkan [25], [40, 15], [30], [50], empat siswa.

Input: pages = [10, 20]students = 3
Output: -1
Penjelasan: Dua buku tidak bisa memberikan satu buku kepada masing-masing dari tiga siswa, jadi jawabannya adalah -1.

Pertanyaan lanjutan

Buktikan bahwa rata-rata bagian, dibulatkan ke atas, ditambah buku paling tebal selalu menjadi batas yang valid. Berapa banyak pemeriksaan yang dihemat oleh batas atas itu pada rak berisi buku-buku tipis?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Ada terlalu banyak cara untuk memotong rak, tetapi menguji satu batas halaman tidak membutuhkan banyak biaya: bagikan buku sesuai urutan di rak, pindah ke siswa berikutnya saat sebuah buku akan melewati batas, lalu hitung jumlah siswa. Batas yang lebih tinggi tidak pernah membutuhkan lebih banyak siswa, jadi batas yang memenuhi syarat membentuk satu rangkaian, dan pencarian biner menemukan titik awalnya.

Naikkan batas halaman satu halaman setiap kali

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Mulai dari L = max(pages), karena seseorang membawa buku paling tebal, lalu naikkan L satu halaman setiap kali sampai jumlah secara greedy sesuai dengan students. Semua batas yang lebih rendah gagal, jadi batas pertama yang sesuai adalah jawabannya. Pada contoh pertama, setiap batas dari 50 hingga 64 membutuhkan empat siswa dan 65 membutuhkan tiga siswa: 16 pemeriksaan.

Jawabannya bisa sebanyak seluruh rak: satu siswa dan 5000 buku dengan 10^5 halaman berarti sekitar 5 × 10^8 batas, masing-masing memeriksa 5000 buku. Pada kolom waktu, A adalah jawabannya dan m adalah buku paling tebal.

Algoritma

Jika students > pages.length, kembalikan -1.
Tulis jumlah greedy untuk batas L: mulai dengan satu siswa dan beban 0; saat load + pages[i] > L, tambahkan satu siswa dan atur beban menjadi pages[i], jika tidak, tambahkan buku ke beban.
Atur L menjadi buku yang paling tebal.
Selama jumlah untuk L lebih dari students, tambahkan 1 ke L.
Kembalikan L.

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

Pencarian biner pada batas halaman

Intuisi

Jumlah siswa dengan pendekatan greedy adalah jumlah siswa paling sedikit yang dapat digunakan oleh pembagian apa pun dengan batas L. Jika dibandingkan siswa demi siswa dengan pembagian lainnya, setiap siswa dalam pendekatan greedy berhenti hanya ketika buku berikutnya tidak muat, sehingga mereka selalu bisa mencapai setidaknya sejauh itu di rak. Jumlah siswa yang lebih sedikit daripada yang tersedia tidak masalah: siswa yang memegang dua buku dapat memberikan satu buku kepada siswa yang tidak memegang buku, dan tidak ada beban yang bertambah.

Jadi, L bisa digunakan tepat ketika jumlah siswa dengan pendekatan greedy paling banyak students. Apa pun yang bisa dilakukan dengan batas L juga bisa dilakukan dengan batas L+1, jadi pencarian biner menemukan batas terkecil yang bisa digunakan.

Rentangnya dimulai dari nilai yang lebih besar antara max(pages) dan jatah rata-rata, yaitu total / students yang dibulatkan ke atas, karena beban terberat setidaknya sebesar kedua nilai tersebut. Batas atasnya adalah total. Pada contoh pertama, rentangnya adalah 54 sampai 160, dan pencarian mencoba 107, 80, 67, 60, 64, 66, dan 65.

Algoritma

Jika students > pages.length, kembalikan -1.
Jumlahkan total dan cari buku yang paling tebal. Tetapkan lo ke nilai yang lebih besar antara buku yang paling tebal dan (total + students - 1) / students, lalu tetapkan hi = total.
Selama lo < hi, ambil mid = lo + (hi - lo) / 2.
Jalankan penghitungan greedy untuk mid. Jika hasilnya paling banyak students, tetapkan hi = mid; jika tidak, tetapkan lo = mid + 1.
Kembalikan lo.

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

Jebakan dan kasus tepi

Melewatkan pemeriksaan -1. Untuk [10, 20] dan 3 siswa, jumlah greedy pada batas 20 adalah 2, jadi pencarian mengembalikan 20.
Memulai rentang hanya dari rata-rata pembagian. Untuk [1, 9] dan 2 siswa, rata-ratanya adalah 5. Pada batas itu, greedy menempatkan buku dengan 9 halaman sendirian, menghitung 2, lalu mengembalikan 5.
Menguji apakah jumlahnya tepat students. Untuk [5, 5, 5, 5, 5, 5] dan 4 siswa, jawabannya adalah 10, dengan jumlah greedy 3.
Mengurutkan buku. [10, 1, 1, 10] dengan 2 siswa menghasilkan 11, tetapi jika diurutkan menjadi [1, 1, 10, 10], hasilnya 12.

Pertanyaan yang sering diajukan3

Apakah Book Allocation Problem sama dengan Split Array Largest Sum?

Ya. Keduanya membagi array menjadi sejumlah blok berurutan yang tidak kosong dan jumlahnya tetap, lalu meminimalkan jumlah terbesar dari sebuah blok. Pencarian biner yang sama dengan pemeriksaan greedy yang sama dapat menyelesaikan keduanya. Versi buku menambahkan kasus -1.

Berapa kompleksitas waktu Masalah Alokasi Buku?

Waktu O(n log S) dan ruang ekstra O(1), dengan n sebagai jumlah buku dan S sebagai total jumlah halaman. Setiap batas yang dicoba memerlukan satu kali penelusuran semua buku, dan pencarian mencoba sekitar log2 S batas: 29 untuk rak dengan 5 × 10^8 halaman.

Kapan buku-buku tidak mungkin dialokasikan?

Hanya jika jumlah siswa lebih banyak daripada jumlah buku, karena setiap siswa membutuhkan setidaknya satu buku. Jika jumlah buku mencukupi, setiap tumpukan yang terdiri dari dua buku atau lebih dapat memberikan buku terakhirnya kepada siswa yang belum memiliki buku, sampai semua siswa memiliki satu buku.

def allocateBooks(pages, students):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan