切換
舊版
前往
大廳
主題

ZeroJudge - d425: 公寓電梯 解題心得

Not In My Back Yard | 2018-08-30 15:50:16 | 巴幣 0 | 人氣 166

題目連結:

題目大意:
給定一個K值(2 < K < 2 ^ 31),表示有一棟K層樓的大樓,並有K-1個學生住在2~K層樓(不會住在同一層樓)。

現有K-1個學生要搭乘電梯,只能選一層樓停,停下來後,學生各自按照自己居住的樓層爬樓梯。每往上一層樓,就有兩點的不滿意度;每往下一層樓,有一點的不滿意度。

求電梯停在哪一樓,可以使不滿意度為最小值。如果有兩個以上的答案,請由小到大輸出。

解題思維:

假設現在所在樓層為X,那麼不滿意度的公式即是:


將上式整合,並對X ^ 2配方,可以發現不滿意度的最小值發生在X=(4K+5)/ 6。

但是因為樓層數為整數,因此要找那一個整數最接近我們求出來的理論上的X值。

直接把上界、下界的值帶進我們上面的方程式判斷何者最小(避免浮點數的誤差),如果一樣就兩者都輸出。如此一來我們便解決了這個題目。


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

創作回應

胖胖貓
往下的不滿意總和是(x+2)(x-1)/2 喔
另外想問一下怎麼求得那個最小值的位置 X=(4K+5)/ 6
是對 k 做微分嗎?
脫離數學太久了 T . T
2018-12-03 00:13:08
Not In My Back Yard
是 (x-1)(x-2)/2 喔,因為走到 x-1 有 1 不滿意值,走到 2 有 x-2 的不滿意值(因為 x-1 ~ 2 有 x-2 個數字)


而配方的過程,可以參見
https://images2.imgbox.com/e2/9b/bzlqn0ly_o.png 這裡XD
2018-12-03 00:36:37
胖胖貓
了解 3Q 話說留言板只能刪除和新增留言而已嗎 沒看到修改的功能
2018-12-03 00:54:03
Not In My Back Yard
不客氣,不過留言區還真的沒有修改的功能QQ
2018-12-03 00:57:10

更多創作