CMU MSIT-SE 2015的青蛙题 FrogPond，求解

stellari 发表于 2015-7-1 21:55
那这就要求能在O(1)时间内得到“考虑A[ i ]的情况下的最远距离”。请问这点该如何做到？我想了一下没有 ...

我感觉O(1)应该搞不到的，上面的例子举了
比如远处先掉一片叶子，这时太远你还不能跳过去
然后近处再落一片，这时你才能一口气从近处跳到远处

stellari 发表于 2015-7-1 21:55
那这就要求能在O(1)时间内得到“考虑A[ i ]的情况下的最远距离”。请问这点该如何做到？我想了一下没有 ...

题目中给了空间复杂度O(X)， 暴力点就开个数组，记录每个位置是否是可达或联通的

满城尽带黄金甲 发表于 2015-7-1 22:19
题目中给了空间复杂度O(X)， 暴力点就开个数组，记录每个位置是否是可达或联通的

要不动手写一个？恕我直言，基本一句话能讲完思路的人，代码写出来都不对。

zhuli19901106 发表于 2015-7-1 22:02
我感觉O(1)应该搞不到的，上面的例子举了
比如远处先掉一片叶子，这时太远你还不能跳过去
然后近处再落 ...

开一个长度X的数组，在循环体中：
{
    讲第i秒降落的叶子所联通的位置置为true;
    青蛙往前走，直到下一位置为false或到达重点为止；
}

满城尽带黄金甲 发表于 2015-7-1 22:25
开一个长度X的数组，在循环体中：
{
    讲第i秒降落的叶子所联通的位置置为true;

X = 100000 D = 50000
令
A[0] = 100000
A[1] = 99999
...
A[99999] = 1
于是在前几万次循环内青蛙不能前进，每次都刷50000级别的位置，TLE了
我考虑的第一个bad case就是这个，还可以有其他的bad case。所以说要用运行才知道，伪代码不打算用来面试吧。

其实还是那句话，讨论算法题感觉不上代码都是白搭，否则表面难度总会低于实际难度。

zhuli19901106 发表于 2015-7-1 22:29
X = 100000 D = 50000
令
A[0] = 100000

请问一下是否有某个OJ可以刷这道题？

zhuli19901106 发表于 2015-7-1 21:24
不对吧，比如X=7，D=2
A[0] = 1
A[1] = 5

用你的例子好了， boolean[] bridge = new boolean[X];
第0秒，叶子降落在位置1， 那么bridge[0]~bridge[2]置为true， 青蛙可以走到位置3；
第1秒，叶子降落在位置5， 那么bridge[4]~bridge[6]置为true， 青蛙原地不动，因为bridge[3]是false；
第2秒，叶子降落在位置3， 那么bridge[2]~bridge[4]置为true， 青蛙可以走到位置7；到终点了

stellari 发表于 2015-7-1 22:32
请问一下是否有某个OJ可以刷这道题？

没有，但我印象中早年在POJ还是哪儿见过类似的青蛙跳问题，可能不大一样吧。

满城尽带黄金甲 发表于 2015-7-1 22:32
用你的例子好了， boolean[] bridge = new boolean[X];
第0秒，叶子降落在位置1， 那么bridge[0]~bridge ...

除了保证算法正确性，还得考虑average case和worst case的效率。我觉得你的思路是对的，不过如果能够找到O(N * D)的worst case，那还是不能AC的。所以建议动手敲一个，然后想一些十万规模的测试数据，尽量追求worst case。
刚才写错了，应该是O(N * D)，此处N和D都可以到10万，所以worst case如果到了这个程度就不可接受了。

zhuli19901106 发表于 2015-7-1 22:29
X = 100000 D = 50000
令
A[0] = 100000

A中的element不能超过X-1，A[0]是不能为100000的，不过没明白你的点在哪，如果是说有重复操作，那么碰到true的位置就停止置位好咯