將鼠標指定給鼠標的最短時間

有n個鼠標和n個孔放置在一條直線上。每個孔只能容納1只鼠標。鼠標可以停留在他的位置，從x移動到x + 1一步，或者從x移動一步到x-1。任何這些動作都會消耗1分鐘。將鼠標指定給鼠標的最短時間

我們需要找到最少的時間，讓所有的老鼠都被分配空位。

實施例：設N = 3和小鼠機體在位置= [4，-4,2]和孔所在的位置[4,0,5]

然後這裏答案爲4

說明：

Assign mouse at position x=4 to hole at position x=4 : Time taken is 0 minutes 
Assign mouse at postion x=-4 to hole at position x=0 : Time taken is 4 minutes 
Assign mouse at postion x=2 to hole at postion x=5 : Time taken is 3 minutes

4分鐘後，所有的小鼠都在洞裏。所以答案是4.

我認爲排序兩個數組，然後找到相應的元素差異將有助於達到目的。但我無法得到一個證明，天氣將是最小的。

所以請幫助。

來源

2014-09-13 user3840069

開始時或移動過程中，是否可以在一個孔中放置多個鼠標？ – Thomas 2014-09-13 16:26:56

@Thomas我們可以假設在同一個位置上不能出現兩個孔。在任何時候它們都不能超過一個鼠標。 – user3840069 2014-09-13 16:28:02

雖然老鼠呢？ – Thomas 2014-09-13 16:28:31

讓i1 < i2成爲兩隻老鼠的位置，並讓j1 < j2成爲兩個孔的位置。這足以通過案例分析表明，

max(|i1 - j1|, |i2 - j2|) <= max(|i1 - j2|, |i2 - j1|),

，因爲它遵循感應每個任務可以通過一系列掉期轉化爲有序分配，其中沒有這些掉期增加完工時間。

來源

2014-09-13 16:32:56

你的意思是我推薦的排序算法是正確的？ – user3840069 2014-09-13 16:33:54

@ user3840069是的。 – 2014-09-13 16:35:38

將鼠標指定給鼠標的最短時間

回答

相關問題