Chocolate Distribution Problem
Bazı çikolata paketlerin var ve packets[i], i paketindeki çikolata sayısını ifade eder. m öğrencinin her biri tam olarak bir paket alır, yani m farklı paket dağıtılır. Dağıtılan en büyük ve en küçük paket arasındaki farkın mümkün olduğunca küçük olması için paketleri seç.
Bu mümkün olan en küçük farkı döndüren minDifference adlı bir fonksiyon yaz.
Fonksiyon
- packetsinteger-array
- her paketteki çikolata sayısı
- minteger
- her biri bir paket alan öğrenci sayısı
- Döndürürinteger
- dağıtılan en büyük ve en küçük paket arasındaki mümkün olan en küçük fark
Kısıtlar
2 ≤ m ≤ packets.length ≤ 1041 ≤ packets[i] ≤ 105- İki pakette aynı sayıda çikolata olabilir.
Örnekler
- Girdi
- packets = [9, 3, 15, 7, 11, 4]m = 3
- Çıktı
- 4
- Açıklama
- Sıralandığında paketler 3, 4, 7, 9, 11 ve 15'tir. Hem 3, 4, 7 hem de 7, 9, 11
4farkını verir ve hiçbir üç paket birbirine daha yakın değildir.
- Girdi
- packets = [20, 5, 18, 6, 19]m = 2
- Çıktı
- 1
- Açıklama
- 5 ve 6 arasındaki fark 1'dir; 18 ve 19 ile 19 ve 20 için de durum aynıdır. Hiçbir iki paket eşit olmadığından, hiçbir çift 1'den daha iyi olamaz.
- Girdi
- packets = [8, 1, 5]m = 3
- Çıktı
- 7
- Açıklama
- Üç öğrenci ve üç paket var, bu yüzden tüm paketler dağıtılır ve fark
8 - 1 = 7olur.
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Dağıtacağınız en küçük paketi zaten bildiğinizi varsayın. Yanına hangi diğer paketler gitmeli?
En küçük paket sabitken, boyut sıralamasında hemen ardından gelen
m-1paketi ver: daha büyük herhangi bir paket aralığı yalnızca genişletir. Sıralı düzende bu paketler yan yana durur.Paketleri sırala. Her
mkomşu paketten oluşan grup, farkı son paketi eksi ilk paketi olan bir penceredir. Pencereyi soldan sağa kaydır ve en küçük farkı koru.
Çözüm
m paketten oluşan her grubu denemek çok yavaştır. En iyi seçim, paketler sıralandıktan sonra her zaman yan yana duran m pakettir. Bu nedenle bir kez sıralayın ve tek bir geçişte, m komşu paketten oluşan herhangi bir pencere boyunca en küçük farkı bulun.
En küçük paketi düzelt
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Dağıttığın en küçük paketi, low değerini sabitle. En büyüğünü küçük tutmak için, en az low büyüklüğünde olan en küçük m-1 paketi al. Böylece fark, en az low büyüklüğündeki m. en küçük paketin büyüklüğünden low çıkarılarak bulunur. Her paketi low olarak dene, kendisine eşit veya daha büyük en az m paket bulunmayanları atla ve en küçük farkı sakla.
n seçeneğin her biri, en fazla n paketi filtreleyip sıralar: O(n² log n). n = 10^4 farklı boyut olduğunda, yalnızca sıralamalar yaklaşık 6 × 10^8 karşılaştırma gerektirir.
Algoritma
bestdeğerini hiçbir yanıtın aşamayacağı bir değerden başlatın.- Her
lowpaketi için, en azlowçikolata içeren tüm paketleri toplayıp sıralayın. - En az
mtane varsa,m. en küçüğündenlowçıkarıldığında elde edilen değer bir adaydır. - En küçük adayı
bestiçinde tutun ve döndürün.
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 bestm paketten oluşan bir pencereyi sırala ve kaydır
Sezgi
Sıralı düzende, sizes[i..i+m-1] penceresinin ilkinde en küçük paket, sonuncusunda ise en büyük paket bulunur; dolayısıyla farkı sizes[i+m-1] - sizes[i] olur.
En iyi seçim her zaman bir pencere olabilir. En küçük ve en büyük paketinin arasında bulunan bir paketi seçim dışında bırakırsan, o paketi en büyük paketin yerine koy. En küçük paket aynı kalır, en büyük paket ise yalnızca küçülebilir; bu yüzden fark hiçbir zaman artmaz. Arada boşluk kalmayana kadar tekrarla.
İlk örnekte üçlü pencerelerin farkları 4, 5, 4 ve 6'dır; dolayısıyla cevap 4'tür. Sıralamanın maliyeti O(n log n), pencereyi kaydırmanın maliyeti ise O(n)'dir.
Algoritma
- Paketleri artan sırada
sizesiçine sıralayın. - İlk pencere için
bestdeğerinisizes[m-1] - sizes[0]olarak ayarlayın. - 1'den
n-mdeğerine kadar heribaşlangıcı içinsizes[i+m-1] - sizes[i]değerinibestile karşılaştırın ve küçük olanı tutun. bestdeğerini döndürün.
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
Tuzaklar ve uç durumlar
- Pencereyi
i+m-1yerinei+mkonumunda bitirmek,m+1paket ölçer. - Bir pencereyi erken durdurmak. Başlangıçlar 0'dan
n-mdahil olmak üzere devam eder.[1, 10, 20, 21]içinm = 2ikeni < n-mkoşuluyla çalışan bir döngü, 1 olan tek farkı kaçırır. - Sıralamayı atlamak.
[9, 3, 15, 7, 11, 4]dizisindeki ilk üç paket 12 fark gösterirken yanıt 4'tür. - Yalnızca ilk pencereyi ölçmek. En küçük
mpaket bir seçenektir, ancak en iyi grup herhangi bir yerden başlayabilir. - Sayıları metin olarak sıralamak. JavaScript'te karşılaştırıcı olmadan
sort(),100000değerini9değerinden önce koyar.
Sıkça sorulan sorular3
Çikolata dağıtımı probleminin zaman karmaşıklığı nedir?
Sıralama O(n log n) zaman alır ve m paketlik pencereyi kaydırmak O(n) zaman alır; dolayısıyla toplam süre O(n log n) olur. Ek alan, sıralanmış bir kopya için O(n) ya da girdiyi yerinde sıralarsanız sıralamanın kendisi dışında O(1) olur.
Çikolata dağıtımı problemi bir kayan pencere problemi midir?
Evet, sıralanmış paketler üzerinde sabit boyutlu bir pencere. Kayan toplam penceresinden farklı olarak, pencere hareket ettikçe güncellenecek hiçbir şey yok: her pencerenin farkı, ilk paketinin son paketinden çıkarılmasıyla elde edilir.
Çikolata dağıtımı problemi sıralama yapılmadan çözülebilir mi?
Buradaki boyutlar en fazla 10^5 olduğundan, sayma sıralaması bunları O(n + 10^5) zamanda sıralar ve aynı yaklaşım izlenir. Boyutlar sınırsız olduğunda, yalnızca karşılaştırmalarla O(n log n) süresinin altına inilemez: m = 2 için yanıt, tam olarak iki paketin eşit olması durumunda 0'dır ve en kötü durumda bir kopyayı saptamak bu sayıda karşılaştırma gerektirir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def minDifference(packets, m):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
packets = [9, 3, 15, 7, 11, 4] m = 3
Beklenen Çıktı
4