|
|
back to boardMy solution runs in O(N logN) and it uses heap data structure. The discussion forums hint that there may be a O(N) time solution. Is there a linear time algorithm? heap?:D
just use lower_bound And, BTW, Yes there is.
At first I used Binary Search on each station but on the next station you can start with the previous index. code:
int canReach1 = A[i] + L1;
while (ind1 <= end && A[ind1] <= canReach1) ind1 ++; i've used dp (which is easy to notice) with some optimization. suppose we have three stations
s1 s2 s3
and there exists path s1-s2 covered with l1, and path s1-s3 also covered with l1. then we can skip the analysis from s2. we can easily reduce used time if we create list of "allowed" stations to analyze (like s3) |
|
|
