广告系统
时间限制：1000 ms  |  内存限制：65536 KB
描述
某广告频道，采用了一种新的广告系统。对于每个广告都有一个给定的价值，该系统总是会从现有的广告中选择价值最高的广告播出。该系统从运行开始每秒钟都会接到一条新广告,只有当新的广告的价值严格大于原来的广告时才会更换广告。


现在按时间顺序给出系统开始的n 秒内接到的广告的价值。要求计算出该广告频道在这段时间内实际播放的广告数量和播放广告数量的期望。

输入
第一行一个整数 T ，表示有T组数据:
对于每组数据有两行：第一行为一个正整数 n (n ≤ 1,000,000) 表示系统运行时间，第二行有 n 个整数，第 i个数表示第 i 秒接到广告的价值。

输出
对于每组测试数据，输出两行: 第一行为一个整数表示实际播放的广告数量，第二行为一个实数表示播放广告数量的期望（期望保留3位小数）。

样例输入
2
1
105448456
2
746865872 354878401
样例输出
1
1.000
1
1.500

http://www.
额，在这个网址提交

那谢谢你啦O(∩_∩)O

我就是不懂期望╮(╯_╰)╭

AC啦，可是为什么概率公式是这个呢？求教

不懂。不是应该是E=1*p1 + 2 *p2 + 3 * p3 + 4*p4 + ... + n * pn 么？我没学过概率统计，希望您讲的更通俗一些
其中 p1 + p2 + ... + pn = 1

[ 本帖最后由 heartnheart 于 2010-7-21 10:42 编辑 ]

原来如此，豁然开朗，爽哉，太谢谢啦O(∩_∩)O哈哈~