創作內容

1 GP

ZeroJudge - d223: 10137 - The Trip 解題心得

作者:Not In My Back Yard│2019-09-21 23:11:48│贊助:2│人氣:31
題目連結:


題目大意:
給定一正整數 n (n ≦ 1000,n = 0 時代表輸入結束),代表有 n 位學生。接著的 n 列,每列給定一個非負兩位小數的浮點數(不會超過 10, 000.00 ),依序代表各個學生在旅途中幫忙支出的金額。

因為有的人出的多、有的人少,因此需要盡可能地平衡各同學的支出(付比較少的要給錢給付比較多的)。如果無法完全平衡金額(不能都支出相同金額),則最多只允許差 0.01 (平衡後,最多與最少的差距)

求最少需要交換多少金額(少的人給多的人錢),才能平衡各同學的支出。



範例輸入:
3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
5
5000.00
11.11
11.11
11.11
11.11
0


範例輸出:
$10.00
$11.99
$3991.11


解題思維:
首先因為要避免浮點數誤差的問題,因此我們需要將輸入的數值 × 100 後當整數處理。

接著我們可以看到,當金額總和 S (乘以 100 後再加總)不是人數 n 的倍數時,最後的平衡金額一定會有人需要多付 1 (原本的 0.01 × 100 後)的錢。

而我們可以藉此得知需要多付 1 的人數即是 S 除以 n 的餘數 r 。而 S 除以 n 的商數 q 是每個人應付的金額。

因為要最小化交換金額,因此令那些本來就付最多的 r 個人最後也多支付 1 的錢(因為付較多的人之金額較為接近「q + 1」的金額)。剩下的人都支付 q 的金額。

最後把所有人的「原本金額 - 最後金額」的值加總(不用判斷誰是多付、誰少付,全部都求差值並加總)除以 200 後即是所求。(除以 100 ,因為要把原本的調整調回來;再多除 2 是因為有多算了一次交換的金額(少給多,只算一次不算做兩次))

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4536543
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

1喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:ZeroJudge - ... 後一篇:ZeroJudge - ...

追蹤私訊

作品資料夾

kisaragi0208大家
難得更新一下了,進來看一下好嗎QQ看更多我要大聲說8小時前


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】