Tembel Kutu Sıralama

Question

Louis'in önünde farklı yiyecekler içeren 10 kutu var: domates, (kırmızı) ringa balığı ve muz.

Kutular bir sıra halinde yan yana dizilmiştir. Son kutunun hemen yanında bu çizgiyi uzatan üç büyük konteyner var. Görevi, bu kutuları yiyeceklere göre sıralanmış kaplara koymaktır. Onun emrinde: sadece yatay olarak hareket edebilen ve her seferinde bir kutuyu kaldırıp indirebilen bir vinç.

Louis kutuları olabildiğince biraz hareket ettirmek istiyor. Herhangi bir şey yapmadan önce, onları kağıda taşımanın en iyi yolunu bulmak için durumunun basitleştirilmiş bir çizimini yapıyor.

Basitleştirilmiş resmi kullanarak, ulaşabileceği tüm kutular tarafından kapsanan en küçük toplam seyahat mesafesi nedir?

Answer 1

Genel asgari seyahat mesafesi:

100

Kanıt:

Toplama değişmeli - @Punintended . Her öğenin orijinal konumundan kaplardaki ilk noktaya taşınması gerekir. Daha sonra her öğenin kaplardaki ilk noktadan doğru noktasına taşınması gerekir. Bu ayrıştırmadan, hangi muzun hangi muz noktasına gittiğinin vb. Önemli olmadığını görürüz. Tüm eşyaları ilk noktaya taşımak gerekir 1+2+3+4+...+10 = 10 * 11/2 = 55. Her eşyayı ilk noktadan doğru yerine taşımak gerekir 0+1+2+3+...+9 = 9*10/2 = 45. Kat edilen toplam mesafe 55+45 = 100.