http://www.spoj.com/problems/ALIEN/
By looking at the constraints we can assume that our solution must be O(NlogN) a worst. but here is a solution with O(N) complexity. First of all we will keep 3 variable which will show us the current answer. we will cal them P and Q and S Let us call them ans1 and ans2 (ans1 stands for the number of people seen and ans2 for the number of stations passed). Our variables P,Q and S show the left and right ends of the interval we are now in and the sum of those numbers. So , every time we need to check if S is smaller than Bt (the maximum number) then we increment Q by 1 and S by A[Q]( we want to check that is it possible to take the next element or not). If at some point we came across a situation where our S (the number of seen people) >Bt (meaning that we took an invalid interval) we are increasing P by 1 and decreasing S by A[P] .
Also at every step we update the values of ans1 and ans2. Also, check the source code for a better understanding.
No comments:
Post a Comment