Aggressive Cows

Q: Apa kompleksitas waktu Aggressive Cows?

Pengurutan membutuhkan O(n log n) dan pencarian biner membutuhkan O(n log D) , dengan D adalah rentang kios dibagi k-1 . Selain salinan yang sudah diurutkan, penggunaan memorinya adalah O(1) .

Q: Mengapa sapi pertama selalu masuk ke kandang paling kiri?

Ambil penempatan mana pun yang berhasil, lalu pindahkan sapi paling kiri ke kandang paling kiri. Sapi itu hanya bergerak menjauh dari sapi-sapi lainnya, jadi tidak ada jarak yang berkurang, dan ada penempatan terbaik yang menggunakan kandang paling kiri.

Q: Bagaimana cara mengenali binary search pada jawabannya?

Pertanyaan ini menanyakan nilai terbesar atau terkecil yang memungkinkan sesuatu terjadi. Memeriksa satu nilai jauh lebih mudah daripada mencari nilai terbaik, dan jawabannya hanya berbalik satu kali saat nilainya bertambah. Di sini, nilainya adalah jarak, dan pemeriksaannya adalah penempatan greedy.

SedangBinary search Pengurutan Greedy

+10

Sebuah kandang memiliki deretan kandang kecil di sepanjang satu garis lurus, dan stalls[i] adalah posisi kandang kecil ke-i. Semua posisinya berbeda dan tidak tersusun dalam urutan tertentu. Kamu harus menempatkan k sapi di k kandang kecil yang berbeda. Sapi-sapi itu bertengkar jika berdiri berdekatan, jadi kamu ingin membuat jarak antara dua sapi terdekat sejauh mungkin.

Kembalikan nilai terbesar yang mungkin untuk jarak terkecil antara dua sapi mana pun.

Fungsi

aggressiveCows(stalls: integer-array, k: integer) → integer

stallsinteger-array: posisi kios yang berbeda, dalam urutan apa pun
kinteger: jumlah sapi yang harus ditempatkan
Mengembalikaninteger: jarak terkecil terbesar yang mungkin antara dua sapi

Batasan

2 ≤ stalls.length ≤ 5000
0 ≤ stalls[i] ≤ 10⁹
Semua posisi di stalls berbeda.
2 ≤ k ≤ stalls.length

Contoh

Input: stalls = [10, 1, 7, 4, 15]k = 3
Output: 6
Penjelasan: Sapi di posisi 1, 7, dan 15 berjarak 6 dan 8. Jarak 7 tidak berhasil: setelah posisi 1, sapi berikutnya ditempatkan di posisi 10, dan tidak ada kandang di posisi 17 atau lebih.

Pertanyaan lanjutan

Apa yang berubah jika kios-kios berdiri membentuk lingkaran, sehingga kios terakhir dalam urutan juga bertetangga dengan kios pertama?

Petunjuk

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

0 dari 3 dibuka

Solusi

Perbaiki sebuah celah dan tanyakan: bisakah k sapi berdiri dengan jarak antara setiap dua sapi setidaknya sebesar itu? Satu kali penelusuran greedy pada kandang yang sudah diurutkan akan menjawabnya. Jawabannya berubah dari ya menjadi tidak satu kali saat celah membesar, jadi binary search menemukan jawaban ya yang terakhir.

Urutkan, lalu coba setiap celah secara bergantian

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Urutkan posisi. Dua sapi yang paling dekat selalu menjadi tetangga, jadi jarak g berlaku jika jarak setiap pasangan sapi yang bertetangga setidaknya g.

Untuk menguji suatu jarak, tempatkan seekor sapi di kandang paling kiri, lalu tempatkan sapi berikutnya di kandang yang berjarak setidaknya g dari kandang sapi terakhir. Penempatan rakus ini dapat menempatkan sapi sebanyak mungkin dibandingkan penempatan mana pun. Sejajarkan penempatan yang berhasil dari kiri: sapi ke-i dalam penempatan rakus tidak pernah berada di sebelah kanan sapi ke-i dalam penempatan tersebut, jadi penempatan rakus menemukan kandang untuk sapi berikutnya tidak lebih lambat.

Jarak 1 selalu berhasil, jadi coba g = 2, 3, ... dan berhenti pada jarak pertama yang menempatkan kurang dari k sapi. Pada contoh pertama, jarak 6 menempatkan 3 sapi dan jarak 7 hanya 2, jadi jawabannya adalah 6.

Dengan dua sapi dan kandang di posisi 0 dan 10^9, diperlukan sekitar 10^9 kali melewati 5000 kandang, atau 5 × 10^12 langkah.

Algoritma

Urutkan posisi.
Tulis pemeriksaan untuk jarak g: satu sapi di pos[0], lalu satu sapi di setiap kandang saat pos[i] - last ≥ g, sambil menghitung jumlah sapi.
Mulai dengan gap = 1.
Selama pemeriksaan untuk gap + 1 menempatkan setidaknya k sapi, tambahkan 1 ke gap.
Kembalikan gap.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    gap = 1  # positions are distinct, so a gap of 1 always fits every cow
    while cowsPlaced(pos, gap + 1) >= k:
        gap += 1
    return gap

Pencarian biner pada celah

Intuisi

Penempatan dengan setiap jarak minimal g+1 juga memiliki setiap jarak minimal g, jadi hasil pemeriksaannya berbunyi ya, ..., ya, tidak, ..., tidak. Pencarian biner menemukan hasil ya yang terakhir.

Mulai pencarian dari lo = 1, yang selalu berhasil, hingga hi = rentang dibagi k-1, dibulatkan ke bawah: k sapi membentuk k-1 jarak di dalam rentang, jadi jarak terkecil tidak mungkin lebih besar. Pemeriksaan yang berhasil menetapkan lo = mid, jadi mid harus dibulatkan ke atas; jika dibulatkan ke bawah, lo = 5 dan hi = 6 akan berulang selamanya.

Pada contoh pertama, rentangnya adalah 14 dan k = 3, jadi hi = 7. Jarak 4 berhasil, jarak 6 berhasil, jarak 7 gagal, dan rentangnya menyempit hingga 6.

Rentang selebar hingga 10^9 menyempit dalam sekitar 30 pemeriksaan terhadap 5000 kandang, kira-kira 150.000 langkah.

Algoritma

Urutkan posisi.
Tetapkan lo = 1 dan hi = (pos[n-1] - pos[0]) / (k-1), dibulatkan ke bawah.
Selama lo < hi, ambil mid = lo + (hi - lo + 1) / 2.
Jika pemeriksaan greedy pada mid menempatkan setidaknya k sapi, tetapkan lo = mid; jika tidak, tetapkan hi = mid - 1.
Kembalikan lo.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    lo = 1  # positions are distinct, so a gap of 1 always works
    hi = (pos[-1] - pos[0]) // (k - 1)  # k-1 gaps share the whole span
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # round up so lo = mid always moves
        if cowsPlaced(pos, mid) >= k:
            lo = mid  # mid fits, so the answer is mid or larger
        else:
            hi = mid - 1  # mid does not fit, so the answer is smaller
    return lo

Jebakan dan kasus tepi

Melewatkan pengurutan. Pada [10, 1, 7, 4, 15] yang belum diurutkan dengan jarak 6, pemeriksaan dimulai dari 10, tidak menemukan kandang berikutnya yang berjarak setidaknya 6, lalu melaporkan satu sapi.
Membulatkan mid ke bawah saat satu iterasi menetapkan lo = mid. Setelah hi = lo + 1, rentangnya tidak lagi menyusut dan perulangan tidak pernah berakhir.
Menguji apakah jumlah sapi tepat k. Pada jarak 1, contoh pertama menempatkan 5 sapi, lebih dari 3, tetapi jarak itu tetap memenuhi syarat. Uji count ≥ k.
Memulai jumlah sapi dari 0. Sapi di kandang paling kiri ikut dihitung, jadi jumlahnya dimulai dari 1.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu Aggressive Cows?

Pengurutan membutuhkan O(n log n) dan pencarian biner membutuhkan O(n log D), dengan D adalah rentang kios dibagi k-1. Selain salinan yang sudah diurutkan, penggunaan memorinya adalah O(1).

Mengapa sapi pertama selalu masuk ke kandang paling kiri?

Ambil penempatan mana pun yang berhasil, lalu pindahkan sapi paling kiri ke kandang paling kiri. Sapi itu hanya bergerak menjauh dari sapi-sapi lainnya, jadi tidak ada jarak yang berkurang, dan ada penempatan terbaik yang menggunakan kandang paling kiri.

Bagaimana cara mengenali binary search pada jawabannya?

Pertanyaan ini menanyakan nilai terbesar atau terkecil yang memungkinkan sesuatu terjadi. Memeriksa satu nilai jauh lebih mudah daripada mencari nilai terbaik, dan jawabannya hanya berbalik satu kali saat nilainya bertambah. Di sini, nilainya adalah jarak, dan pemeriksaannya adalah penempatan greedy.

def aggressiveCows(stalls, k):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

stalls = [10, 1, 7, 4, 15]
k = 3

Output yang diharapkan