作者raincole (冷雨)
看板Prob_Solve
標題[問題] UVa 11637
時間Wed Oct 28 10:41:45 2009
http://uva.onlinejudge.org/contests/231-f349ee18/11637.pdf
我對題目的理解是：
有一個長度 N 的序列
將它隨機重新排列
如果其中兩個元素在原序列和新序列中的距離皆不大於 K
則將此兩元素視為「浪費的」
要求出「浪費的」元素的總數的期望值
（原序列是頭尾相接的，但新序列不是）
以N = 312 K = 1的情形而言
我的算法如下：
先考慮中間的319個元素之一A，A在原序列中有2個元素距離不大於1，在新序列中也有2個
故A是「浪費的」的機率為 1 - 318/320 * 317/319
又考慮端點的2個元素之一B，B在原序列中有2個元素距離不大於1，在新序列中只有1個
故B是「浪費的」的機率為 1 - 319/320 * 318/319
所以總期望值：
(1 - 318/320 * 317/319) * 319 + (1 - 319/320 * 318/319) * 2 = 3.99375
應輸出 3.9938
但是UVa toolkit上輸入312 1的答案是3.9937
我想不通這個算法哪裡不對...
請版上高手指教
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 113.61.199.94
→ raincole:對了 應該不是精度問題 我用maple求過了 10/28 10:43
推 ledia:看不出有什麼問題 @@ 10/28 12:02
→ raincole:可是還是WA掉了... 10/28 12:55
推 Fenikso:N=10 K=4, 你會輸出14 很明顯不合理 10/28 22:43
推 Fenikso:至於浮點數那個不要太在意XD 換個os就不一樣了 10/28 23:25
→ raincole:喔喔 謝謝提醒...不過應該不是錯在那裡... 10/28 23:56
→ raincole:因為他比較亂我想說先修一下在貼上來 結果不小心修錯了 10/28 23:57
→ raincole:不過他的10 4是10.0000 可是還是WA掉otz 10/28 23:58
※ 編輯: raincole 來自: 113.61.199.94 (10/29 00:05)