主題
題目連結(jié)：
題目意譯：
你被給定一正整數(shù)陣列 beans，其中每個整數(shù)代表著在某一個魔法袋子中含有的魔法豆子之?dāng)?shù)量。
請從每個袋子移除掉若干顆（可能沒有）魔法豆子，使得每個剩下的非空袋子（至少還包含一顆豆子）內(nèi)含的豆子數(shù)量相同。一旦一顆豆子從一個袋子中移除後，你不得將其放回至任意一個袋子中。
回傳你最少所需移除的魔法豆子之?dāng)?shù)量。
限制：
1 ≦ beans.length ≦ 10 ^ 5
1 ≦ beans[i] ≦ 10 ^ 5
範(fàn)例測資：
範(fàn)例 1：
輸入： beans = [4,1,6,5]
輸出： 4
解釋：
- 我們從只有 1 顆豆子的袋子中移除 1 顆豆子。
剩餘袋子的現(xiàn)況：[4,0,6,5]
- 接著我們從有 6 顆豆子的袋子中移除 2 顆。
剩餘袋子的現(xiàn)況：[4,0,4,5]
- 接著我們從有 5 顆豆子的袋子中移除 1 顆。
剩餘袋子的現(xiàn)況：[4,0,4,4]
我們總共移除 1 + 2 + 1 = 4 顆豆子使得剩下的非空袋子皆有著相同數(shù)量的袋子。
沒有其他可以移除 4 顆或更少的豆子之解法存在。
範(fàn)例 2：
輸入： beans = [2,10,3,2]
輸出： 7
解釋：
- 我們從有 2 顆豆子的袋子中移除 2 顆豆子。
剩餘袋子的現(xiàn)況：[0,10,3,2]
- 接著我們從另一個有 2 顆豆子的袋子中移除 2 顆。
剩餘袋子的現(xiàn)況：[0,10,3,0]
- 接著我們從有 3 顆豆子的袋子中移除 3 顆。
剩餘袋子的現(xiàn)況：[0,10,0,0]
我們總共移除 2 + 2 + 3 = 7 顆豆子使得剩下的非空袋子皆有著相同數(shù)量的袋子。
沒有其他可以移除 7 顆或更少的豆子之解法存在。
解題思維：
我們先把每一個袋子按照其內(nèi)含豆子數(shù)由大排到小，因此目前第一個袋子中的豆子數(shù)最多。
可以看到如果在最佳移除的策略下最後是剩下 x 個非空的袋子，則這 x 個袋子在原本排序後的狀態(tài)下將會是前 x 個袋子（也就是前 x 個豆子最多的）。因為如果是其他的袋子，代表前 x 個袋子中最後會有變成空的袋子存在，而這是不理想的（因為一定不會比較好，甚至可能會比原先的解法還糟）。
而現(xiàn)在我們不知道這個 x 之值，只知道必定是前 x 個袋子。因此我們可以選擇窮舉 x——從前一個、前兩個、……、到所有袋子都留著的情況（也就是 x 將會從 1 跑到 beans.length）。然後把每一種 x 之值算出在該種狀態(tài)下最少的移除豆子數(shù)，取其中的最小值即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
