題目連結:
題目大意:
給定一個K值(2 < K < 2 ^ 31),表示有一棟K層樓的大樓,並有K-1個學生住在2~K層樓(不會住在同一層樓)。
現有K-1個學生要搭乘電梯,只能選一層樓停,停下來後,學生各自按照自己居住的樓層爬樓梯。每往上一層樓,就有兩點的不滿意度;每往下一層樓,有一點的不滿意度。
求電梯停在哪一樓,可以使不滿意度為最小值。如果有兩個以上的答案,請由小到大輸出。
解題思維:
假設現在所在樓層為X,那麼不滿意度的公式即是:
將上式整合,並對X ^ 2配方,可以發現不滿意度的最小值發生在X=(4K+5)/ 6。
但是因為樓層數為整數,因此要找那一個整數最接近我們求出來的理論上的X值。
直接把上界、下界的值帶進我們上面的方程式判斷何者最小(避免浮點數的誤差),如果一樣就兩者都輸出。如此一來我們便解決了這個題目。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。