Aggressive Cows

Q: Aggressive Cows'un zaman karmaşıklığı nedir?

Sıralama O(n log n) , ikili arama ise O(n log D) zaman alır; burada D , ahırların kapladığı aralığın k-1 'e bölünmesiyle elde edilir. Sıralanmış bir kopya dışında bellek kullanımı O(1) 'dir.

Q: İlk inek neden her zaman en soldaki ahıra girer?

İşe yarayan herhangi bir yerleşimi al ve en soldaki ineğini en soldaki bölmeye taşı. Bu inek yalnızca diğerlerinden uzaklaşır; dolayısıyla hiçbir mesafe kısalmaz ve en iyi yerleşimlerden biri en soldaki bölmeyi kullanır.

Q: Cevap üzerinde ikili aramayı nasıl fark edersiniz?

Soru, bir şeyin mümkün olduğu en büyük veya en küçük değeri soruyor; tek bir değeri kontrol etmek, en iyisini bulmaktan çok daha kolay ve değer arttıkça yanıtlar yalnızca bir kez değişiyor. Burada değer aralık, kontrol ise açgözlü yerleştirmedir.

Ortaİkili arama Sıralama Açgözlü

+10

Bir ahırda tek bir düz çizgi boyunca ahır bölmeleri bulunur ve stalls[i], i. bölmenin konumudur. Konumların hepsi farklıdır ve belirli bir sırada verilmemiştir. k ineği k farklı bölmeye yerleştirmelisin. İnekler birbirine yakın durduklarında kavga eder; bu yüzden birbirine en yakın iki ineği olabildiğince uzağa yerleştirmek istiyorsun.

Herhangi iki inek arasındaki en küçük mesafenin alabileceği en büyük değeri döndür.

Fonksiyon

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

stallsinteger-array: birbirinden farklı durak konumları, herhangi bir sırada
kinteger: yerleştirilecek inek sayısı
Döndürürinteger: iki inek arasındaki mümkün olan en büyük en küçük mesafe

Kısıtlar

2 ≤ stalls.length ≤ 5000
0 ≤ stalls[i] ≤ 10⁹
Tüm stalls konumları birbirinden farklıdır.
2 ≤ k ≤ stalls.length

Örnekler

Girdi: stalls = [10, 1, 7, 4, 15]k = 3
Çıktı: 6
Açıklama: 1, 7 ve 15 numaralı ahırlardaki inekler arasında sırasıyla 6 ve 8 birim mesafe vardır. 7 birimlik aralık işe yaramaz: 1'den sonra sıradaki inek 10'a yerleşir ve 17'de veya daha ileride hiçbir ahır yoktur.

Ek soru

Tezgâhlar bir daire üzerinde durursa ne değişir; böylece sıradaki son tezgâh, ilk tezgâhın da komşusu olur?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bir aralık belirleyip şunu sor: Her iki ineğin arasında en az bu kadar mesafe olacak şekilde k inek yerleştirilebilir mi? Sıralanmış ahırlar üzerinde yapılacak tek bir açgözlü geçiş bu soruyu yanıtlar. Aralık büyüdükçe yanıt bir kez evetten hayıra döner; bu yüzden ikili arama son evet değerini bulur.

Sırala, ardından her boşluğu sırayla dene

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

Sezgi

Konumları sırala. En yakın iki inek her zaman komşu olur; bu nedenle komşu ineklerin arasındaki mesafe en az g olduğunda g aralığı geçerlidir.

Bir aralığı sınamak için en soldaki bölmeye bir inek, ardından da son ineğin en az g ötesindeki her bölmeye bir inek yerleştir. Bu açgözlü yerleştirme, mümkün olan tüm yerleştirmeler arasında en fazla sayıda ineği sığdırır. Geçerli herhangi bir yerleştirmeyi soldan hizala: açgözlü yerleştirmedeki i. inek, o yerleştirmedeki i. ineğin asla sağında olmaz; bu yüzden açgözlü yöntem bir sonraki ineği en geç o ineğin yerleştirildiği bölmeye yerleştirebilir.

1 aralığı her zaman geçerlidir; bu yüzden g = 2, 3, ... değerlerini dene ve ilk olarak k inekten daha azını yerleştiren aralıkta dur. İlk örnekte 6 aralığı 3 inek, 7 aralığı ise yalnızca 2 inek yerleştirir; dolayısıyla yanıt 6'dır.

İki inek ve 0 ile 10^9 konumlarında bölmeler olduğunda, 5000 bölme üzerinde yaklaşık 10^9 geçiş, yani 5 × 10^12 adım gerekir.

Algoritma

Konumları sıralayın.
g aralığı için kontrolü yazın: pos[0] konumunda bir inek, ardından pos[i] - last ≥ g koşulunu sağlayan her ahırda bir inek olacak şekilde inekleri sayın.
gap = 1 ile başlayın.
gap + 1 için yapılan kontrol en az k inek yerleştiriyorsa gap değerini 1 artırın.
gap değerini döndürün.

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

Aralıkta ikili arama

Sezgi

Her boşluğu en az g+1 olan bir yerleşimde, her boşluk en az g de olur; bu nedenle kontroller evet, ..., evet, hayır, ..., hayır şeklindedir. İkili arama son eveti bulur.

Her zaman işe yarayan lo = 1 değerinden başlayıp hi değerini aralığın k-1'e bölünüp aşağı yuvarlanmış hâli olarak belirleyin: k inek, aralığın içinde k-1 boşluk bırakır; dolayısıyla en küçük boşluk bundan büyük olamaz. Kontrol başarılı olursa lo = mid olarak ayarlanır; bu yüzden mid yukarı yuvarlanmalıdır. Aşağı yuvarlanırsa lo = 5 ve hi = 6 sonsuza kadar tekrarlanır.

İlk örnekte aralık 14 ve k = 3 olduğundan hi = 7 olur. Boşluk 4 başarılıdır, boşluk 6 başarılıdır, boşluk 7 başarısızdır ve aralık 6'da kapanır.

10^9 genişliğe kadar olan bir aralık yaklaşık 5000 ahır bölmesi üzerinde 30 kontrolde kapanır; bu da kabaca 150.000 adımdır.

Algoritma

Konumları sırala.
lo = 1 ve hi = (pos[n-1] - pos[0]) / (k-1) değerlerini ayarla; aşağı yuvarla.
lo < hi olduğu sürece mid = lo + (hi - lo + 1) / 2 değerini al.
mid değerindeki açgözlü kontrol en az k inek yerleştiriyorsa lo = mid olarak ayarla; aksi hâlde hi = mid - 1 olarak ayarla.
lo değerini döndür.

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

Tuzaklar ve uç durumlar

Sıralamayı atlamak. Sıralanmamış [10, 1, 7, 4, 15] dizisinde, aralık 6 iken kontrol 10'dan başlar, ondan 6'dan daha uzakta başka bir ahır bulamaz ve bir inek olduğunu bildirir.
Bir geçiş sırasında lo = mid atanırken mid değerini aşağı yuvarlamak. hi = lo + 1 olduktan sonra aralık küçülmeyi durdurur ve döngü hiç bitmez.
Tam olarak k inek olup olmadığını kontrol etmek. Aralık 1 iken ilk örnekte 5 inek yerleştirilir; bu sayı 3'ten fazladır, ancak aralık işe yarar. count ≥ k koşulunu kontrol et.
İnek sayısını 0'dan başlatmak. En soldaki ahırdaki inek de sayılır, bu yüzden sayaç 1'den başlar.

Sıkça sorulan sorular3

Aggressive Cows'un zaman karmaşıklığı nedir?

Sıralama O(n log n), ikili arama ise O(n log D) zaman alır; burada D, ahırların kapladığı aralığın k-1'e bölünmesiyle elde edilir. Sıralanmış bir kopya dışında bellek kullanımı O(1)'dir.

İlk inek neden her zaman en soldaki ahıra girer?

İşe yarayan herhangi bir yerleşimi al ve en soldaki ineğini en soldaki bölmeye taşı. Bu inek yalnızca diğerlerinden uzaklaşır; dolayısıyla hiçbir mesafe kısalmaz ve en iyi yerleşimlerden biri en soldaki bölmeyi kullanır.

Cevap üzerinde ikili aramayı nasıl fark edersiniz?

Soru, bir şeyin mümkün olduğu en büyük veya en küçük değeri soruyor; tek bir değeri kontrol etmek, en iyisini bulmaktan çok daha kolay ve değer arttıkça yanıtlar yalnızca bir kez değişiyor. Burada değer aralık, kontrol ise açgözlü yerleştirmedir.

def aggressiveCows(stalls, k):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı