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

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

你的意思是每处理一个A[ i ]，就将bridge[A[ i ]]及其周围共 D+1个元素设为true？那样的话，总时间复杂度不应该是O(ND)么？

满城尽带黄金甲 发表于 2015-7-1 22:38
A中的element不能超过X-1，A[0]是不能为100000的，不过没明白你的点在哪，如果是说有重复操作，那么碰到t ...

等你的代码咯，咱们毕竟不是在辩论。

                int curr = 0;
                for(int i = 0; i < N; i++){
                        if(A[i] > curr && A[i] <= curr + D)
                                curr = A[i];
                        System.out.println(curr);
                        if(curr + D >= X)
                                return i;
                }
                return -1;

我不是科班出身的，我正在学算法，所以我肯定有很多地方没考虑到，欢迎各位指正。

stellari 发表于 2015-7-1 22:39
你的意思是每处理一个A[ i ]，就将bridge[A[ i ]]及其周围共 D+1个元素设为true？那样的话，总时间复杂 ...

没错，感觉问题就在这儿。能够保证不整段重复赋值，不整段重复检查，才能是O(N)。

stellari 发表于 2015-7-1 22:39
你的意思是每处理一个A[ i ]，就将bridge[A[ i ]]及其周围共 D+1个元素设为true？那样的话，总时间复杂 ...

并不需要O(ND)， 因为碰到下一个是true的话，那后面D个都已经设置了，不需要置位，整个循环下来，最多就是把X的每个位置set了一遍，X的range和N一样的咯，那么应该是O(2N)，所以还是O(N)

georgmaster 发表于 2015-7-1 22:44
int curr = 0;
                for(int i = 0; i < N; i++){
                        if(A > curr && A = X)

如果一开始一片叶子落在很远的地方，那就没被处理，等于是被丢弃了。所以这个思路应该不对。

比如你站在位置0 ，能跳2格远。第1秒的时候位置5来了一片叶子，虽然现在你跳不到，但之后可能跳到。

而你的算法直接把这个5给扔了。

zhuli19901106 发表于 2015-7-1 22:49
如果一开始一片叶子落在很远的地方，那就没被处理，等于是被丢弃了。所以这个思路应该不对。

比如你站 ...

谢谢，是我疏忽了。那我现在只能想到这个ＤＮ的了.
(自动隐藏【i】是什么鬼！)

if(X <= D)
                        return 0;
                int curr = 0;
                boolean[] isLeaf = new boolean[X+1];
                int time = 0;
                isLeaf[A[time]] = true;
                isLeaf[X] = true;
                while(true){
                        for(int i = curr+D; i > curr; i--){
                                if(i > X)
                                        continue;
                                if(isLeaf){
                                        curr = i;
                                        break;
                                }
                        }
                        System.out.println(curr);
                        if(curr == X){
                                return time;
                        }
                        time++;
                        if(time > N-1)
                                break;
                        isLeaf[A[time]] = true;        
                }
                return -1;

满城尽带黄金甲 发表于 2015-7-1 22:49
并不需要O(ND)， 因为碰到下一个是true的话，那后面D个都已经设置了，不需要置位，整个循环下来，最多就 ...

比如跳2格远
现在[3, 5]已经是true，然后位置4来了一片叶子？
这时起始位置4已经是true，如何处理？
还有一个情况：
跳4格远
现在[3, 7] [9, 13]已经是true，然后位置6来了一片叶子，首尾都是true，但是中间的8还是false，如何处理？

georgmaster 发表于 2015-7-1 22:44
int curr = 0;
                for(int i = 0; i < N; i++){
                        if(A > curr && A = X)

这个算法仅适用于“第K次的落叶位置肯定大于前K-1次落叶的位置”的情况。而这道题的难点在于落叶的位置可以是任意的。比如
A = {0, 4, 2}; D = 2, X = 5
你的代码第一次遇到0，curr不动；第二次遇到4，由于不在curr一步能到达的范围内，curr还是不动；第三次遇到2，此时curr等于2，但是curr + D = 4不大于X。于是循环就这样结束了，返回-1。而这种情况的正确答案应该是2.

zhuli19901106 发表于 2015-7-1 22:52
比如跳2格远
现在[3, 5]已经是true，然后位置4来了一片叶子？
这时起始位置4已经是true，如何处理？

这个倒是问到我了，这种case如果依然要这么搞的话，我的想法的话就是只能放弃primitive的int，弄个class/structure，一个位置是一个Point这样的结构了，这样好不爽。。。。容我三四p.s. sb了，直接加D看是不是true，逆着set……