ETH官方钱包

前往
大廳
主題

LeetCode - 0517. Super Washing Machines 解題心得

Not In My Back Yard | 2024-05-04 12:00:17 | 巴幣 0 | 人氣 66

題目連結:


題目意譯:
你有 n 臺超級洗衣機排成一列。一開始,每臺洗衣機有若干件(可能為空)的洋裝。

在每一步中,你可以選定任意 m 臺(1 ≦ m ≦ n)洗衣機,並從每一臺把其中一件洋裝同時傳給各自相鄰洗衣機中的其中一者。

給定一個整數陣列 machines,其代表著從左至右的每一臺洗衣機中各自容納的洋裝數量。回傳最少所需的步數來使每一臺都容納相同數量的洋裝;如果這不可能做到,則回傳 -1。

限制:
n == machines.length
1 ≦ n ≦ 10 ^ 4
0 ≦ machines[i] ≦ 10 ^ 5



範例測資:
範例 1:
輸入: machines = [1,0,5]
輸出: 3
解釋:
第一步:    1     0 <-- 5    =>    1     1     4
第二步:    1 <-- 1 <-- 4    =>    2     1     3
第三步:    2     1 <-- 3    =>    2     2     2

範例 2:
輸入: machines = [0,3,0]
輸出: 2
解釋:
第一步:    0 <-- 3     0    =>    1     2     0
第二步:    1     2 --> 0    =>    1     1     1

範例 3:
輸入: machines = [0,2,0]
輸出: -1
解釋:
不可能使三臺洗衣機都擁有同樣數量的洋裝。


解題思維:
首先,如果所有洗衣機的洋裝數量總和不是 n 的倍數,則不可能將洋裝平均分配給每一臺洗衣機;如果是則一定有辦法可以平均分配,因為最少也可以一件一件地來移動這些洋裝。



接著我們先計算出目標洋裝數為何,可以看到其值即為「所有洋裝數」除以 n,令該值為 T。

再來,我們掃過一次陣列 machines,並算出所有的 Di = machines[i] - T 之值。

可看到當 Di > 0 時,代表該洗衣機一定會把洋裝分送出去(注意這不代表該洗衣機不會接受到其他臺的洋裝),可以看作是「供給方」;而當 Di < 0 時,則代表該洗衣機一定會得到其他臺的洋裝(一樣,這不代表著該洗衣機不會把洋裝分送出去),可以看作是「需求方」;至於 Di == 0,則就只是個暫存般的空間,可能會得到洋裝,也可能會分送洋裝出去。

「供給方」一次只會送一件洋裝出去,而「需求方」可以同時接受左右兩邊洗衣機的洋裝。因此最少步數至少會是「供給方」中最大者,可簡單寫為 max(Di)(因為「需求方」是負數,因此在取最大值時會直接被正數和 0 覆蓋掉)。



再接著,我們可以觀察洋裝的「流向」(即淨傳遞方向)來發現到除了「供給方」以外的洗衣機,洋裝的「流向」會是固定的。

例如說 1 2 2 3 2 2 1 這個例子中,3 左側的數字的洋裝流向會是往左(準確來說是洋裝會從右側來,為了方便稱呼而簡化為此。因此注意以下所「往左」或「往右」不一定代表著洋裝必定會往左或往右「出去」);而 3 右側的則是往右。

因此我們要求最少步數的話,需要考慮其中最大的「流量」。

要算「流量」很簡單,只要多一個變數 B 在算 Di 的過程中即可。這個 B 會將過程中的 Di 逐漸地加總,即 B 會從 D0 變成 D0 + D1;再變成 D0 + D1 + D2……以此類推。而在算出 Di 時的 B 值(注意該值已加上 Di)即代表著洗衣機 i 的「流向」以及「流量」,其中 B > 0 代表往右 、 B < 0 代表往左 、 B == 0 就代表不會流動,而流量即為 |B|。

而該值會代表「流量」和「流向」的這個「命題」可以用數學歸納法證明。不過這邊用比較直白的方式描述(本質上還是數學歸納法,但不正式):
    可以看到算完 D0 後的 B 會使命題成立。因為如果 D0 > 0,則其會往右且流量為 D0;如果 D0 < 0,則其會往左且流量為 -D0。
    
    接著如果算出 D1 並使 B 變為 D0 + D1 的話會有以下四種情況:
        一,D0 和 D1 都大於 0,此時流向往右(因為 D0 和 D1 都是「供給方」)且流量為 D0 + D1;

        二,D0 和 D1 都小於 0,則類似上面的情況。此時流向往做且流量為 -(D0 + D1);

        三,D0 + D1 > 0,則代表著「應付」完 D0 的流量(這可能代表著 D0 洋裝超級多,滿足完 D1 的需求後還需要往右送;又或是 D0 缺一些洋裝,從洗衣機 1 分送一點之後還有要往右送的部份)後還有多的洋裝要往右送,且流量為 D0 + D1;

        四,D0 + D1 < 0,類似情況三。此時的流向為往左且流量為 -(D0 + D1)。

    再來的 D2 、 D3 ……也是以此類推。

而整個過程中 |B| 的最大值即為最大流量,而該值再與先前的 max(Di) 之值比大小取最大值即為所求最少步數。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作