문제

Here is an interview problem about balls rolling towards buckets from Sprinklr Interview Experience at GeekforGeeks.

You are given $n$ balls on the table and all the balls are rolling towards the one end of the table with velocities $V_1, V_2, \dots, V_n$ and there is a bucket placed at that end. The distance of the ball with velocity $V_i$ from the end of the table where the bucket is placed is $D_i$. It is given that when two balls collide, both balls merge into each other and move with the velocity of the ball nearer to the bucket. So, at last, you have two tell the number of the balls which will fall into the bucket.

Here is what I am doing. First, I insert one extra ball in the array with zero velocity and distance zero. That is, I am inserting the bucket as a ball. We will find how many balls are getting merged with last ball.

Find a pair of adjacent balls which have the smallest value of $T = \frac{D_i - D_{i+1}}{V_i - V_{i+1}}$ and $V_i > V_{i+1}$ and remove ball with velocity $V_i$, that is, the first ball in the pair. Now for each remaining ball, reduce its distance by its velocity times $T$, and continue doing this process.

The number of time we will choose the bucket as the second ballwill be the final answer.

Can anyone suggest a better approach? My approach has time complexity of $O(n^2)$.

올바른 솔루션이 없습니다

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top