Sunday, December 22, 2013

SPOJ 16793. Statistics applied

Here is the problem statement
http://www.spoj.com/problems/EC_ESTA/

We have a long sequence and every time it is asked we need to print the median of it. ( The median is the middle number of a sorted sequence, if the length of the sequence is an even number => it has 2 medians fo the real median is the sum of those middle elements divided on 2). For solving it we will divide the sequence into 2 parts. We need to keep each part in a priority queue. (For more information about priority queue go here). The elements of the second priority queue will be stored with a - (minus) sign so that every timew we call for the largest ellement we get the smallest element in the second sequence which wil be the biggest element in priority queue when multiplied with -1.As we can get the biggest element of the first queue (which might be the middle element) and the biggest element (which also might be the middle element) if the total size is even number than we take this 2 values and sum them and print the result divided on 2 if not then we just output the biggest number of the first queue. (PAY a very close attention when you are adding the element, you need to add it to the appropriate place or else this strategy won't work). Make sure to check the source code for better understanding.

       DOWNLAOD THE FULL SOURCE CODE

       


No comments:

Post a Comment