codechef walk解決方案背後的解釋

解決codechef問題WALK我想出了一個算法來解決這個問題，使用分而治之的方法，根據我的算法，我們在數組中找到最大值並將我們的數組分成兩部分一個從開始到最大元素，另一半從下一個到最大元素到數組的末尾），然後我們使用以下方法找到數組的第一部分（部分參與最大元素）的初始速度：Max + （n-1）其中n是陣列中該部分的元素數量....我們對陣列的每個部分都做這件事，並且在計算每個部分的初始速度之後，我們檢查零件的初始速度的數組小於或等於Max + 1，其中Max是在考慮中的部分之前的數組部分的最大元素，如果這是我們什麼都不做的事情，我們會發現Max + 1和初始速度之間的差異，並將該差異添加到正在考慮的部件之前的部件的初始速度，並且我們繼續重複此過程，直到不再需要更改。現在這個算法肯定會工作，但它會超過時間限制..當我看到編輯它有這個問題的一個線路解決方案..有人可以解釋我的解決方案，我無法理解它。在此先感謝。codechef walk解決方案背後的解釋

來源

2016-01-09 tkhurana96

設初始速度爲V. 當它們在第一個（基於0的索引）車間時，它們的速度仍然是V，並且V> = W1。當他們穿過它去第二家店鋪時，速度變成V-1。我們知道V-1> = W2。同樣當他們穿過它去第三家店鋪時，速度變成V-2。我們知道V-2> = W3。繼續這種方式，我們看到，這種關係成立：六> =無線對於所有的i在[0，N-1]

V0 >= W0 + 0 
V1 >= W1 + 1 
V2 >= W2 + 2 
V3 >= W3 + 3 ...

因此，VI> =無線+ I對於所有的i。

選擇V作爲其最大在所有無線+我

來源

2016-01-09 19:04:01

能否請您細說「選擇V作爲其最大所有Wi +我之間」 ......我的意思是，爲什麼我們需要選擇最大的V？ – tkhurana96

，因爲這個條件必須對所有的i維持** Vi> = Wi + i **。如果您在所有這樣的Vi中選擇最大值，則該條件保證始終保持不變 –

codechef walk解決方案背後的解釋

回答

相關問題