作者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
1F：→ raincole:对了 应该不是精度问题 我用maple求过了 10/28 10:43
2F：推 ledia:看不出有什麽问题 @@ 10/28 12:02
3F：→ raincole:可是还是WA掉了... 10/28 12:55
5F：推 Fenikso:N=10 K=4, 你会输出14 很明显不合理 10/28 22:43
6F：推 Fenikso:至於浮点数那个不要太在意XD 换个os就不一样了 10/28 23:25
7F：→ raincole:喔喔 谢谢提醒...不过应该不是错在那里... 10/28 23:56
9F：→ raincole:因为他比较乱我想说先修一下在贴上来 结果不小心修错了 10/28 23:57
10F：→ raincole:不过他的10 4是10.0000 可是还是WA掉otz 10/28 23:58
※ 编辑: raincole 来自: 113.61.199.94 (10/29 00:05)