- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
这个问题摘自interviewstreet.com
Given array of integers Y=y1,...,yn, we have n line segments such that endpoints of segment i are (i, 0) and (i, yi). Imagine that from the top of each segment a horizontal ray is shot to the left, and this ray stops when it touches another segment or it hits the y-axis. We construct an array of n integers, v1, ..., vn, where vi is equal to length of ray shot from the top of segment i. We define V(y1, ..., yn) = v1 + ... + vn.
For example, if we have Y=[3,2,5,3,3,4,1,2], then v1, ..., v8 = [1,1,3,1,1,3,1,2], as shown in the picture below:
For each permutation p of [1,...,n], we can calculate V(yp1, ..., ypn). If we choose a uniformly random permutation p of [1,...,n], what is the expected value of V(yp1, ..., ypn)?
Input Format
First line of input contains a single integer T (1 <= T <= 100). T test cases follow.
First line of each test-case is a single integer N (1 <= N <= 50). Next line contains positive integer numbers y1, ..., yN separated by a single space (0 < yi <= 1000).
Output Format
For each test-case output expected value of V(yp1, ..., ypn), rounded to two digits after the decimal point.
Sample Input
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 6Sample Output
4.33
3.00
4.00
6.00
5.80
11.15Explanation
Case 1: We have 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. Average of these values is 4.33.
Case 2: No matter what the permutation is, V(yp1, yp2, yp3) = 1+1+1 = 3, so the answer is 3.00.
Case 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, and average of these values is 4.00.
对于 N=50 的问题,一个天真的解决方案将永远运行。我相信这个问题可以通过为每根棍子独立计算一个值来解决。我仍然需要知道是否有任何其他有效的方法来解决这个问题。我们必须在什么基础上独立计算每根棍子的值(value)?
最佳答案
我们可以解决这个问题,方法是:
if the k th stick is put in i th position, what is the expected ray-length of this stick.
那么问题可以通过将所有位置的所有棍子的所有预期长度相加来解决。
设 expected[k][i]
是第 k 个棍子放在第 i 个位置的预期射线长度,令 num[k][i][length]
是第 k 个棍子放在第 i 个位置且光线长度等于的排列数长度
,然后
expected[k][i] = sum( num[k][i][length] * length ) / N!
如何计算num[k][i][length]
?例如,对于 length=3
,考虑下图:
...GxxxI...
其中 I
是位置,3 'x' 表示我们需要 3 个严格低于 I
的棍子,而 G
表示我们需要一根至少和 I
一样高的棍子。设 s_i
是小于第 k
个木棍的木棍数量,g_i
是大于或等于第 k
个木棍的木棍数量到第k
根,然后我们可以选择g_i
中的任意一个放在G
位置,我们可以选择任意length
的 s_i
来填充 x
位置,所以我们有:
num[k][i][length] = P(s_i, length) * g_i * P(n-length-1-1)
如果 I
之前的所有位置都小于 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
关于algorithm - 如何应对 Vertical Sticks 挑战?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10040609/
我将 bxSlider 用于轮播。它提供水平和垂直模式,这很好。 唯一的问题是在垂直显示时,箭头仍然保持在水平位置。 HTML 代码: JS $('.sliderLo
我有一个包含数百个 STL 网格的文件夹,我想使用 flatten 命令将它们合并到 meshlab 中。 我使用的是常规 GUI,当我打开文件并选择所有这些 STL 文件时,如果我想“统一重复顶点”
我有 2 个表,其中包含一组数据,如下所示,我想获得结果,该结果将在字段 balance 中进行计算: 我卡在了 balance 字段,如何让 balance 运行? tblIn in_date
我想打印所有顶点及其相邻顶点。我在网上找到了一些关于如何做到这一点的例子,但它对我不起作用。我收到错误,++ 运算符不能用于 ai。另外我认为它需要是 vertex_idMap[*ai] 而不是 ve
运行 ./gradlew lint 向我报告一个令人困惑的错误: 39: Must be one of: RecyclerView.HORIZONTAL, RecyclerView.VERTICAL
你好,我无法弄清楚为什么传递 GLfloat 位置数组 (xyz) 的第一个元素突然为缓冲区提供该数组的所有元素。 glBufferData(GL_ARRAY_BUFFER, sizeof(Verte
抱歉打死马,但我无法理解为什么下面的方法不起作用。 设置line-height: 50px 设置vertical-align: top 据我了解,这应该使行框高 50 像素,然后 vertical-a
所以,我正在查看 Bootstrap 文档以寻找解决这个问题的方法,但没有找到任何东西。有没有办法,使用bootstrap组件,一个接一个垂直显示按钮组? 这是我目前所拥有的: but
目标:我需要通过移动现有顶点而不是添加新顶点来编辑矢量图层,因为我有一个表格,其中显示每个顶点的坐标。当我移动一个顶点时,我必须更新表格。 调查:我查看了 openlayers 4.6.5 的文档 I
这两个属性是一样的还是有不同的用法?vertical-align:top 和 vertical-align:text-top 最佳答案 区别可以通过line-height属性来解释。 MDN Sour
我有一些关于视觉内容的问题,可以在附件(在 Firefox 中使用 CTRL-+ 查看放大的视觉内容在左侧生成它的代码)。让我们命名视觉从上到下用数字 1、2、3、4、5 和 6 列出的内容。我对这种
XCode 建议我在创建的动态大小单元格中为约束设置垂直压缩和拥抱优先级。虽然单元格总是正确显示,但错误仍然存在,所以这不是问题,但我需要删除错误才能将更新提交到 App Store。 我在多标签
显示部分幻灯片的垂直 Flexslider。幻灯片从上到下剪切。这是不同图像尺寸的问题。 这是代码: $(window).load(function(){ $('.flexslider').f
我正在尝试 CSS multi-columns spec 并想出了 column-axis。但我不明白它的作用是什么?看起来 column-axis: horizontal; 是 regular
在思考这个问题时,我一直在挠头。我有 3 个 div。顶部和底部的 div 有一个最小高度,中间的 div 有未知的高度(按内容扩展)但应该在页面中居中。顶部和底部的 div 应填充剩余的顶部和底部空
我有一个包含文本的 div,line-height 大于文本的高度。这意味着每行文本的顶部和下方都有空间。 右侧有一个垂直边框,我希望其顶部与文本顶部对齐。我需要以某种方式将文本与其行的顶部对齐。 这
嗯,我得到了这个结构: #parent{ max-width: 800px; height: auto; margin: auto;
我这里有两个可能很简单的 CSS 问题: http://web288.merkur.ibone.ch/klingler/ 如何让页脚中的 © Klingler Fahrzeugtechnik AG 2
假设我们有一组 JSON 格式的人。每个实体大约有 100 个属性。使用 ng-repeat 的标准方法: ... Attribute1 Attribute2 ... Attribu
我正在尝试用点语言绘制一个稀疏矩阵,实际上节点连接是可以的,但问题是这些节点的垂直对齐,我尝试使用 pos 并放置具有 x 和 y 值的节点,但只是没有t 工作(我认为是因为默认布局)。如果你能帮助我
我是一名优秀的程序员,十分优秀!