Chocolate Distribution Problem

Q: Apa kompleksitas waktu dari masalah pembagian cokelat?

Pengurutan membutuhkan O(n log n) dan menggeser jendela berisi m paket membutuhkan O(n) , jadi totalnya O(n log n) . Ruang tambahan yang diperlukan adalah O(n) untuk salinan yang sudah diurutkan, atau O(1) di luar pengurutan itu sendiri jika kamu mengurutkan input langsung.

Q: Apakah masalah distribusi cokelat merupakan masalah sliding window?

Ya, jendela berukuran tetap di atas paket yang sudah diurutkan. Tidak seperti jendela jumlah berjalan, tidak ada yang perlu diperbarui saat jendela bergerak: selisih setiap jendela diperoleh dengan mengurangkan paket pertamanya dari paket terakhirnya.

Q: Apakah masalah pembagian cokelat bisa diselesaikan tanpa pengurutan?

Ukuran di sini paling besar 10^5 , jadi counting sort mengurutkannya dalam waktu O(n + 10^5) dan argumen yang sama berlaku. Untuk ukuran yang tidak dibatasi, perbandingan saja tidak bisa mengalahkan O(n log n) : dengan m = 2 , jawabannya tepat 0 jika dua paket sama, dan mendeteksi duplikat membutuhkan sebanyak itu perbandingan dalam kasus terburuk.

MudahPengurutan Sliding window

+10

Kamu memiliki beberapa bungkus cokelat, dan packets[i] adalah jumlah cokelat dalam bungkus i. Setiap siswa dari m siswa mendapat tepat satu bungkus, sehingga m bungkus yang berbeda dibagikan. Pilih bungkus-bungkus tersebut agar selisih antara bungkus terbesar dan terkecil yang dibagikan sekecil mungkin.

Tulis fungsi bernama minDifference yang mengembalikan selisih terkecil yang mungkin.

Fungsi

minDifference(packets: integer-array, m: integer) → integer

packetsinteger-array: jumlah cokelat di setiap bungkus
minteger: jumlah siswa, masing-masing mendapat satu paket
Mengembalikaninteger: selisih sekecil mungkin antara paket terbesar dan terkecil yang dibagikan

Batasan

2 ≤ m ≤ packets.length ≤ 10⁴
1 ≤ packets[i] ≤ 10⁵
Dua bungkus dapat berisi jumlah cokelat yang sama.

Contoh

Input: packets = [9, 3, 15, 7, 11, 4]m = 3
Output: 4
Penjelasan: Setelah diurutkan, paket-paket itu adalah 3, 4, 7, 9, 11, dan 15. Baik 3, 4, 7 maupun 7, 9, 11 memiliki selisih 4, dan tidak ada tiga paket yang jaraknya lebih dekat.

Input: packets = [8, 1, 5]m = 3
Output: 7
Penjelasan: Ada tiga siswa dan tiga paket, jadi semua paket dibagikan dan selisihnya adalah 8 - 1 = 7.

Petunjuk

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

0 dari 3 dibuka

Solusi

Mencoba setiap kelompok yang terdiri dari m paket terlalu lambat. Pilihan terbaik selalu terdiri dari m paket yang bersebelahan setelah paket diurutkan. Jadi, urutkan sekali, lalu jawabannya adalah selisih terkecil di antara setiap jendela yang terdiri dari m paket bersebelahan, yang ditemukan dalam satu kali lintasan.

Perbaiki paket terkecil

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Tetapkan paket terkecil yang kamu bagikan sebagai low. Agar paket terbesar tetap kecil, ambil m-1 paket terkecil yang ukurannya setidaknya low. Selisihnya adalah paket terkecil ke-m yang ukurannya setidaknya low, dikurangi low. Coba setiap paket sebagai low, lewati paket yang memiliki kurang dari m paket dengan ukuran setidaknya sebesar itu, lalu simpan selisih terkecil.

Setiap dari n pilihan menyaring dan mengurutkan hingga n paket: O(n² log n). Dengan n = 10^4 ukuran yang berbeda, proses pengurutan saja memerlukan sekitar 6 × 10^8 perbandingan.

Algoritma

Atur best ke nilai yang tidak mungkin dilampaui oleh jawaban mana pun.
Untuk setiap paket low, kumpulkan semua paket yang berisi setidaknya low cokelat, lalu urutkan.
Jika jumlahnya setidaknya m, nilai paket terkecil ke-m dikurangi low menjadi kandidat.
Simpan kandidat terkecil di best, lalu kembalikan nilainya.

def minDifference(packets, m):
    best = max(packets) - min(packets)  # no gap can be wider than this
    for low in packets:
        # The packets that could go out alongside low, smallest first (low is one of them).
        bigger = sorted(x for x in packets if x >= low)
        if len(bigger) >= m:
            best = min(best, bigger[m - 1] - low)
    return best

Urutkan dan geser jendela berisi m paket

Intuisi

Dalam urutan terurut, jendela sizes[i..i+m-1] memiliki paket terkecil di awal dan paket terbesar di akhir, sehingga selisihnya adalah sizes[i+m-1] - sizes[i].

Pilihan terbaik selalu bisa berupa jendela. Jika suatu pilihan melewatkan paket yang berada di antara paket terkecil dan terbesar, tukar paket itu dengan paket terbesar. Paket terkecil tetap sama dan paket terbesar hanya bisa mengecil, sehingga selisihnya tidak pernah bertambah. Ulangi sampai tidak ada celah yang tersisa.

Pada contoh pertama, jendela berukuran tiga menghasilkan 4, 5, 4, dan 6, jadi jawabannya adalah 4. Pengurutan membutuhkan O(n log n) dan penggeseran membutuhkan O(n).

Algoritma

Urutkan paket secara menaik ke dalam sizes.
Tetapkan best ke sizes[m-1] - sizes[0], jendela pertama.
Untuk setiap titik awal i dari 1 hingga n-m, bandingkan sizes[i+m-1] - sizes[i] dengan best dan pertahankan nilai yang lebih kecil.
Kembalikan best.

def minDifference(packets, m):
    sizes = sorted(packets)
    best = sizes[m - 1] - sizes[0]
    # The window sizes[i..i+m-1] holds m packets; its first is the smallest, its last the largest.
    for i in range(1, len(sizes) - m + 1):
        best = min(best, sizes[i + m - 1] - sizes[i])
    return best

Jebakan dan kasus tepi

Mengakhiri jendela pada i+m, bukan i+m-1, sehingga mengukur m+1 paket.
Menghentikan perulangan satu jendela terlalu awal. Posisi awal berjalan dari 0 hingga n-m, termasuk nilai tersebut. Untuk [1, 10, 20, 21] dengan m = 2, perulangan dengan i < n-m melewatkan satu-satunya selisih sebesar 1.
Melewatkan pengurutan. Dalam [9, 3, 15, 7, 11, 4], tiga paket pertama memiliki selisih 12, sedangkan jawabannya adalah 4.
Hanya mengukur jendela pertama. m paket terkecil adalah salah satu pilihan, tetapi kelompok terbaik bisa dimulai dari mana saja.
Mengurutkan angka sebagai teks. Dalam JavaScript, sort() tanpa pembanding menempatkan 100000 sebelum 9.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari masalah pembagian cokelat?

Pengurutan membutuhkan O(n log n) dan menggeser jendela berisi m paket membutuhkan O(n), jadi totalnya O(n log n). Ruang tambahan yang diperlukan adalah O(n) untuk salinan yang sudah diurutkan, atau O(1) di luar pengurutan itu sendiri jika kamu mengurutkan input langsung.

Apakah masalah distribusi cokelat merupakan masalah sliding window?

Ya, jendela berukuran tetap di atas paket yang sudah diurutkan. Tidak seperti jendela jumlah berjalan, tidak ada yang perlu diperbarui saat jendela bergerak: selisih setiap jendela diperoleh dengan mengurangkan paket pertamanya dari paket terakhirnya.

Apakah masalah pembagian cokelat bisa diselesaikan tanpa pengurutan?

Ukuran di sini paling besar 10^5, jadi counting sort mengurutkannya dalam waktu O(n + 10^5) dan argumen yang sama berlaku. Untuk ukuran yang tidak dibatasi, perbandingan saja tidak bisa mengalahkan O(n log n): dengan m = 2, jawabannya tepat 0 jika dua paket sama, dan mendeteksi duplikat membutuhkan sebanyak itu perbandingan dalam kasus terburuk.

def minDifference(packets, m):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

packets = [9, 3, 15, 7, 11, 4]
m = 3

Output yang diharapkan