---

一、 將 O(n!) 降到大約 O((n!)/((n-k)!)/2)

對於 n=25,k=4 的情況來說計算量差了 102181884343418880000 倍，

暴力解 n=25,k=4 的情況估計 1 萬年也算不完。

 

做完這步，k ≦ 3 及 k=4,n<20 的情況應該都會 AC，

k=4,n=25 大約還要算10秒左右。

 

令 m = n - k，為住戶的個數，

住戶依題目輸入的順序依序編號為 0, 1, ... , m-1。

 

首先假設 k 個公共設施的樓層位置為已知，

計算將 m 個住戶安排到剩下的 m 個樓層中的所有排列的最佳解 x。

 

剩下的 m 個樓層由下而上依序重新編號為 0, 1, ... , m-1。

令 S 為一個 m*m 的矩陣，

S[i][j] 表示第 j 個住戶的在第 i 個樓層滿意度。

為方便下面說明，設值 S[i][j] = -1 時表示該數字被消除。

 

則有

(a). 至少存在一組排列 a₀,a₁,...,a_m-1 使得 min { S[i][a_i], 0 ≦ i < m } = x

(b). 對於任意排列  a₀,a₁,...,a_m-1 皆滿足 min { S[i][a_i], 0 ≦ i < m } ≦ x

換言之，

(c). 不存在排列 a₀,a₁,...,a_m-1 使得 min { S[i][a_i], 0 ≦ i < m } > x 且 S[i][a_i] ≠ -1, 0 ≦ i < m

 

因此，我們可以由以下步驟求得 x，

 

1. 設計一 function f(S) 使得

若存在一組排列 a₀,a₁,...,a_m-1 使得 min { S[i][a_i], 0 ≦ i < m } = x 且 S[i][a_i] ≠ -1, 0 ≦ i < m

則 f(S) = 1

 

若不存在排列 a₀,a₁,...,a_m-1 使得min { S[i][a_i], 0 ≦ i < m } = x 且 S[i][a_i] ≠ -1, 0 ≦ i < m

則 f(S) = 0

 

由 (a), (b), (c) 可知

當被消除的數字小於 x 時，f(S) = 1

當被消除的數字大於等於 x 時，f(S) = 0

 

2. 由小至大依序消除，每消除一個數字就計算一次 f(S)，

當第一次計算到 f(S) = 0 時，

該次消除的數字即為此次最佳解 x。

 

3. 若此次最佳解比當前最佳解大，則取代之

 

至此 m 個樓層不管怎麼排都只要計算一次 S 矩陣，

所以大約相當於 O((n!)/((n-k)!))

又因將樓層安排上下反轉的情況是同樣的解不需計算，所以再少一半

最終大約相當於 O((n!)/((n-k)!)/2)

 

二、略過不需計算的排列

令當前最佳解為 inf，

若接下來要計算的排序所對應的 S 矩陣中，

存在任一列或任一行，該列或該列的數字最大值不超過 inf，則不需計算此次的排列，

因題目"使得滿意度最低住戶的滿意度盡可能地高"，所以此排列不會有更好的解。

 

 

三、f(S) 的設計

有點類似用位元運算解八皇后，但不用考慮斜向。

這點就留給大家思考啦~

做完此三點就可以AC此題了。

 

 

四、

其實還有一些可以略過的計算的地方，不過說明起來有些麻煩，加上也省沒多少時間就懶得打了。

大概就是 k 個公共設施相對位置固定情況下去平移，考慮需要計算的範圍。