1

这个问题取自interviewstreet.com

给定整数数组 Y=y1,...,yn，我们有 n 个线段，使得线段 i 的端点是 (i, 0) 和 (i, yi)。想象一下，从每个段的顶部向左发射一条水平射线，当它接触到另一个段或到达 y 轴时，这条射线停止。我们构造了一个由 n 个整数组成的数组，v1, ..., vn，其中 vi 等于从片段 i 的顶部射出的射线的长度。我们定义 V(y1, ..., yn) = v1 + ... + vn。

例如，如果我们有 Y=[3,2,5,3,3,4,1,2]，那么 v1, ..., v8 = [1,1,3,1,1,3,1, 2]，如下图所示：

在此处输入图像描述

对于 [1,...,n] 的每个排列 p，我们可以计算 V(yp1, ..., ypn)。如果我们选择 [1,...,n] 的均匀随机排列 p，那么 V(yp1, ..., ypn) 的期望值是多少？

输入格式

输入的第一行包含一个整数 T (1 <= T <= 100)。T 测试用例如下。

每个测试用例的第一行是一个整数 N (1 <= N <= 50)。下一行包含由单个空格分隔的正整数 y1, ..., yN (0 < yi <= 1000)。

输出格式

对于 V(yp1, ..., ypn) 的每个测试用例输出预期值，四舍五入到小数点后两位数。

样本输入

6
3
1 2 3
3
3 3 3
3
2 2 3
4
10 2 4 4
5
10 10 10 5 10
6
1 2 3 4 5 6

样本输出

4.33
3.00
4.00
6.00
5.80
11.15

解释

案例 1：我们有 V(1,2,3) = 1+2+3 = 6, V(1,3,2) = 1+2+1 = 4, V(2,1,3) = 1+ 1+3 = 5, V(2,3,1) = 1+2+1 = 4, V(3,1,2) = 1+1+2 = 4, V(3,2,1) = 1 +1+1 = 3。这些值的平均值为 4.33。

情况2：不管排列是什么，V(yp1, yp2, yp3) = 1+1+1 = 3，所以答案是3.00。

情况 3：V(y1 ,y2 ,y3)=V(y2 ,y1 ,y3) = 5, V(y1, y3, y2)=V(y2, y3, y1) = 4, V(y3, y1, y2 )=V(y3, y2, y1) = 3，这些值的平均值为 4.00。

对于 N=50，一个简单的问题解决方案将永远运行。我相信这个问题可以通过独立计算每根棍子的值来解决。我仍然需要知道是否有任何其他有效的方法来解决这个问题。我们必须在什么基础上独立计算每根棍子的价值？

4

3 回答 3

7

我们可以通过以下方式解决这个问题：

如果第k根棍子放在第i个位置，那么这根棍子的预期射线长度是多少。

然后可以通过将所有位置的所有棒的所有预期长度相加来解决问题。

设第k根棍子放置在第i个位置expected[k][i]的预期射线长度，设 是第k根棍子放置在第i个位置且射线长度等于的排列数，则num[k][i][length]length

expected[k][i] = sum( num[k][i][length] * length ) / N!

如何计算num[k][i][length]？例如，对于length=3，请考虑下图：

...Gxxx我...

位置在哪里I，3 'x' 意味着我们需要 3 根严格低于的棍子I，并且G意味着我们需要一根至少与 一样高的棍子I。设s_i小于k第 th 根的棍g_i数为 大于等于k第 th 根的棍数，则可以选择任意一个 g_i放置，G我们可以选择任意填充位置，所以我们有：lengths_ix

num[k][i][length] = P(s_i, length) * g_i * P(n-length-1-1)

如果之前I的所有位置都较小 then I，我们不需要更大的坚持G，即xxxI....，我们有：

num[k][i][length] = P(s_i, length) * P(n-length-1)

这里有一段 Python 代码可以解决这个问题：

def solve(n, ys):
    ret = 0
    for y_i in ys:
        s_i = len(filter(lambda x: x < y_i, ys))
        g_i = len(filter(lambda x: x >= y_i, ys)) - 1

        for i in range(n):
            for length in range(1, i+1):
                if length == i:
                    t_ret = combination[s_i][length] * factorial[length] * factorial[ n - length - 1 ] 
                else:
                    t_ret = combination[s_i][length] * factorial[length] * g_i * factorial[ n - length - 1 - 1 ]
                ret += t_ret * length

    return ret * 1.0 / factorial[n] + n
于 2013-03-03T15:47:55.017 回答
7

这是与https://cs.stackexchange.com/questions/1076/how-to-approach-vertical-sticks-challenge相同的问题，我的答案（比前面给出的更简单）是：

想象一个不同的问题：如果你必须k在槽中放置相同高度的棍子，n那么棍子之间的预期距离（以及第一根棍子和名义槽0之间的期望距离，以及最后一根棍子和名义槽之间的期望距离n+1）是(n+1)/(k+1)因为有k+1间隙适合长度n+1。

回到这个问题，一根特定的棍子对有多少根棍子（包括它自己）一样高或更高感兴趣。如果是这样k，那么之前的预期差距也是如此 (n+1)/(k+1)。

所以算法只是简单地为每根棍子找到这个值并将期望值相加。例如，从高度 开始，3,2,5,3,3,4,1,2具有更大或相等高度的棒的数量是5,7,1,5,5,2,8,7这样的期望是9/6+9/8+9/2+9/6+9/6+9/3+9/9+9/8 = 15.25。

这很容易编程：例如 R 中的一行

V <- function(Y){(length(Y) + 1) * sum(1 / (rowSums(outer(Y, Y, "<=")) + 1) )}

给出原始问题中样本输出中的值 

> V(c(1,2,3))
[1] 4.333333
> V(c(3,3,3))
[1] 3
> V(c(2,2,3))
[1] 4
> V(c(10,2,4,4))
[1] 6
> V(c(10,10,10,5,10))
[1] 5.8
> V(c(1,2,3,4,5,6))
[1] 11.15
于 2013-08-23T22:05:38.420 回答
1

正如您正确地指出的那样，我们可以为每根棍子独立解决问题。

令 F(i, len) 是排列数，来自棒 i 的射线正好是 len。
那么答案是

（总和（由 i，len）F（i，len）*len）/（n！）

剩下的就是计算 F(i, len)。设 a(i) 为棒数 j，即 y_j<=y_i。b(i) - 棒数，即 b_j>b_i。

为了获得长度为 len 的光线，我们需要有这样的情况。

B, l...l, O  
   len-1 times

其中O - 是棒#i。B - 坚持更大的长度，或开始。l - 坚持高度，小于 ith。

这给了我们2种情况：
1）B是开始，这可以通过P(a(i), len-1) * (b(i)+a(i)-(len-1))!多种方式实现。
2）B是更大的棍子，这可以通过P(a(i), len-1)*b(i)*(b(i)+a(i)-len)!*(n-len)多种方式实现。

编辑：将 b(i) 更正为 (mul) 中的第 2 项，以代替案例 2 中的 a(i)。

于 2012-04-06T08:17:36.343 回答