TopCoder算法：BrightLamps - n燈

我讀過其他解決方案和想法，但我不明白他們。

以下是mnbvmar的想法，能否詳細解釋一下，您認爲是正確的？

如果你翻車了兩個連續的K-元素序列（即，(i, i + 1, ..., i + K - 1)和(i + 1, ..., i + K)），只有兩個燈得到切換（i和i + K）。

現在關鍵是要注意，每一個可能的組合做K - 元素翻轉，也可以用以下兩種實現：

撥動第一K燈，

切換任何兩個燈距離K。

（每個切換K連續燈是這些操作的複合）。現在更簡單了。當然，每個操作都可以完成零次或一次（不止一次）。

比方說，我們沒有使用最佳解決方案中的第一個操作。然後我們的序列溶解到K遠處的元素序列K，其中您可以切換兩個連續的元素。這很容易解決;如果i第 - 個序列具有偶數個關閉的燈，則可以將它們全部打開;在相反的情況下，很明顯我們不能全部打開它們，但是可以在序列中僅留下最低價值的燈。

如果我們使用第一個操作該怎麼辦？然後，我們只需切換第一個K燈，然後執行與以前完全相同的步驟。

來源

2015-09-06 loverszhaokai

這是什麼，你不明白在這裏？ – vish4071

比方說，我們有10個燈A-J和k=4。然後我們可以翻轉下面的任何X序列：

ABCDEFGHIJ 
XXXX   //flip starting at A, changes A,B,C,D 
XXXX  //flip starting at B, changes B,C,D,E 
    XXXX  //... 
    XXXX 
    XXXX 
    XXXX

。

如果我們執行從燈「S」開始的翻轉序列，緊接着從S的燈右側開始的翻轉序列，例如， d和E，我們可以看到比一些燈具翻轉兩次，只有第一個和最後一個受影響的一個永久改變（即保持不變。）：

ABCDEFGHIJ 
    XXXX  //this 
    XXXX  //and this together 

    X X  //is the same as this alone

兩個翻轉序列後，只有d和H是不同的從以前;
E，F，G翻轉兩次=不變。所以，使用這種模式，
它可以改變只有兩個燈k距離（在這種情況下4），
而不是k燈。
。

現在，在A上使用此模式也會改變E，並在E上使用它。在A，E以外的燈上使用它，我不會影響A，E，I。 ...換句話說，可以將k（4）組中的所有（10）個燈分開：

A,E,I 
B,F,J 
C,G 
D,H

它們是完全獨立的，即，獨立計算每個組的最優解將給我們提供總體最優解（只要我們記得使用上面的開關模式）。
。

在一組內，我們考慮AEI，我們可以考慮使用更小規模的相同模式，即。一個影響E和E影響我（如上面說的），以及可能的翻轉模式是

ABCDE 
xx 
xx 
    xx 
    xx

也許你現在看到的，與鏈接這些模式，我們即使翻轉任意兩個燈這一組中，他們不是連續的，只要它是兩個燈。 IE瀏覽器。 AB或AC或AD或AE或BC等
現在，獲取真實的數據，如果關閉的燈的數量是偶數，您可以按照上述方式打開對，直到所有的燈都熄滅，然後該組完成。如果數字不均勻，請選擇最低值的燈作爲唯一保持關閉的燈。

來源

2015-09-06 10:52:14 deviantfan

但是，這裏有一個問題**「選擇最低值的燈作爲唯一保持關閉的燈」**。當init'string =「001000001」'，'a [] = {1000,3,10,8,999,7,4,6,998,10}'時，它會失敗。 'AEI'是'000'，值是'{1000,999,998}'，因爲數字是3，這是奇數，所以我們應該丟棄最低的'998'，**但是它非常大其他**。顯然，在這種情況下，我們不能丟棄最低的一個。 – loverszhaokai

@loverszhaokai這意味着你只是發現從「mnbvmar」的解決方案是不是最佳:)（其實，我沒有想到那麼久：p） – deviantfan

是的。我不知道爲什麼「mnbvmar」的解決方案可以得到正確的答案。例如'init string =「00001」'，'a [] = {1,1,1,2}'和'K = 4'，在「mnbvmar」的解決方案中，第一組是「 01「，值爲{1，2}'，我們應該丟棄最低的那個'1'，但顯然我們不能丟棄它，最好的方法是切換前4位，這將是所有「11111」。 – loverszhaokai

TopCoder算法：BrightLamps - n燈

回答

相關問題