2012年12月8日 星期六

[UVA] 10137 The Trip

基本想法如下:由於允許最後分帳差距在1 cent內,所以全部人出的金額只可能有兩種:X跟 X+0.01,所有金額的加總S等於重分配之前的總合。假設有N人,X = floor(S / N),而多少人出X+0.01 ? N' = (S * 100 ) % N。知道X及N'後,求transaction總合就簡單了。

input雖然長得很像double,但是考慮到之後的運算其其都是整數運算 (以cent為單位),最好的作法還是把全部金額都看成int。只要把value * 100 即可。機車的地方在於,如果你用 cout >> aDoubleNumber 那你就吃屎了,因為乘100之後的整數位數是不準的,會有one cent offset。比較蠢但是穩的作法便是讀字串進來然後parse成int。output 也不要依賴 cout float_precision,自己印小數點吧!