MJ [37] Cross River

一道用叶子过河题 - 未名空间(mitbbs.com)
- A bug is trying to cross the river start from position 0 to position X
- Every time bug can jump no more than the D steps (1 to D steps);
- Leaves will fall from the tree to the river based on schedule A. A[0] = 1
means a leaf will fall on position 1 at time 0;
- Need to find the earliest time that the bug can jump from position 0 to x
using leaves; If there is no answer, return -1;

Example:
A = [1, 3, 1, 4, 2, 5]
X = 7
D = 3

Answer: 3
Explanation: At time 3, there will be leaves on position 1,3, and 4; bug can
jump 1 step, 3 step, and then 3 steps to cross the river;

Expected time complexity is O(n)
http://likemyblogger.blogspot.com/2015/09/mj-37.html

int jump1(int X, int D, vector<int> A){

    int cur = 0;

    priority_queue<int, vector<int>, greater<int>> leavesPositions;

    for(int i=0; i<A.size(); ++i){

        leavesPositions.push(A[i]);

        while(!leavesPositions.empty() && cur+D>=leavesPositions.top()){

            cur = max(leavesPositions.top(), cur);

            leavesPositions.pop();

        }

        if(cur+D>=X) return i;

    }

    return -1;

}

 

int main(){

    //vector<int> A = {5, 2};

    vector<int> A = {1,3,1,4,2,5};

    cout<<jump1(7, 3, A)<<endl;

    return 0;

}

http://massivealgorithms.blogspot.com/2015/07/codility-frogriverone-solution.html
Read full article from 一道用叶子过河题 - 未名空间(mitbbs.com)