Pada garis bilangan panjang M
, di mana 0 < M <= 1,000,000,000
, Anda memberikan N
( 1 < N <= 100,000
) pasangan bilangan bulat poin. Dalam setiap pasangan, titik pertama mewakili di mana objek saat ini berada, dan titik kedua mewakili di mana objek harus dipindahkan. (Perlu diingat second
poinnya mungkin lebih kecil dari first
).
Sekarang, anggap Anda mulai dari titik 0
dan memiliki gerobak yang dapat menampung 1
objek. Anda ingin memindahkan semua objek dari posisi awal mereka ke posisi akhir masing-masing saat menempuh jarak paling sedikit di sepanjang garis angka ( bukan perpindahan). Anda harus tepat sasaran M
.
Sekarang, saya sudah mencoba untuk mengurangi masalah ini menjadi masalah yang lebih sederhana. Sejujurnya aku bahkan tidak bisa memikirkan solusi brute force ( mungkin serakah). Namun, pemikiran pertama saya adalah untuk merosotkan gerakan mundur ke dua gerakan maju, tetapi itu tampaknya tidak berhasil dalam semua kasus.
Saya membuat 3
contoh kasus uji ini di sini:
Jawaban untuk testcase pertama adalah 12
. Pertama, Anda mengambil red
item di titik 0
. Kemudian Anda pindah ke titik 6
(jarak = 6
), jatuhkan red
item sementara, lalu ambil green
item. Kemudian Anda pindah ke titik 5
(jarak = 1
) dan menjatuhkan green
item. Kemudian Anda kembali ke titik 6
(jarak = 1
) dan mengambil red
item yang Anda jatuhkan, pindah ke titik 9 (jarak = 3
), lalu pindah ke titik 10
(jarak = 1
) untuk menyelesaikan urutan.
Total jarak yang ditempuh adalah 6 + 1 + 1 + 3 + 1 = 12
, yang merupakan jarak minimum yang memungkinkan.
Dua kasus lain punya jawaban 12
, saya yakin. Namun, saya tidak dapat menemukan aturan umum untuk menyelesaikannya.
Ada yang punya ide?
sumber
Jawaban:
Jika Anda kosong, mulailah bergerak ke kanan.
Setiap kali Anda mencapai objek dan Anda kosong, ambil (duh) dan bergerak menuju tujuannya.
Setiap kali Anda mencapai suatu objek
a
dan Anda sudah membawab
, selalu pilih objek mana yang memiliki tujuan terkecil secara numerik (paling jauh ke kiri).Jika Anda belum berada di M, kembali ke langkah 1.
Ini optimal: Satu-satunya tempat di mana Anda memiliki pilihan nyata adalah dalam langkah 3. Menangani tujuan paling kiri terlebih dahulu memastikan bahwa pada saat Anda mengirim kedua objek, Anda akan sejauh mungkin ke kanan.
Mengapa pertanyaan ini ada di programmers.sx? Ya, "pertanyaan wawancara", tapi itu hanya teka-teki yang bagus.
PS. Dalam hal implementasi, yang Anda butuhkan adalah daftar tugas (pasangan integer poin) yang diurutkan berdasarkan posisi awal.
sumber
Misalkan Anda diberikan gerakan ini
(a, b), (c, d), (e, f), ...
maka jarak minimum yang harus Anda tempuh adalahabs(b - a) + abs(d - c) + abs(f - e) + ...
dan jarak sebenarnya yang Anda tempuhabs(b - a) + abs(c - b) + abs(d - c) + abs(e - d) + ...
.Pada dasarnya, diberikan array gerakan, intinya adalah untuk meminimalkan fungsi "jarak perjalanan" dengan menukar elemen di sekitarnya. Jika Anda menganggap kombinasi tertentu sebagai simpul dan semua kombinasi yang dapat Anda capai darinya sebagai tepian, Anda dapat menggunakan salah satu dari banyak algoritma pencarian grafik yang memanfaatkan heuristik. Salah satu contohnya adalah pencarian balok .
sumber
Mungkin saya salah memahami masalah tetapi bagaimana dengan yang berikut ini:
Fakta bahwa itu diurutkan menjamin bahwa Anda tidak bolak-balik elemen untuk menempatkan mereka di lokasi yang tepat (terlepas dari apakah garis tersebut diwakili sebagai array atau daftar)
Perbarui setelah komentar @templatetypedef:
Gunakan a
HashTable
untuk menyimpan semua pasangan. Gunakan lokasi saat ini dari setiap pasangan sebagai kunci indeks.Gunakan indeks kedua di atas pasangan.
sumber
Kecenderungan saya pada suatu algoritma yang pada dasarnya serakah:
Buat daftar poin yang perlu dipindahkan. Karena mengoptimalkan ini bukan bagian dari masalah yang diperlukan, saya tidak akan khawatir mengaturnya.
Saya pikir ini mencakup semua kasus. Dalam arti itu rekursif tetapi melalui memperbarui daftar itu daripada memanggil dirinya sendiri.
sumber
Destination = SubList.FindSmallest(Location, Move.Origin)
? Apa yangMove.Origin
diwakili?Ini adalah masalah salesman keliling yang asimetris . Anda dapat menganggap ini sebagai grafik. Tepi akan menjadi masing-masing (mulai, selesai) pasangan, satu untuk setiap (0, mulai), dan semua pasangan lainnya (selesai, mulai).
Dengan asumsi NP! = P, itu akan memiliki waktu berjalan yang diharapkan eksponensial.
sumber
M
titik akhir dari garis bilangan?N
bisa 100.000.