The problem has two ideas :
1- ensuring that sum does not exceed some value : x.
2- median adjustment. __ first notice that we cant solve this problem by filling our vector with value >= y ; why ? because he said that sum must not exceed value : x.
So,to solve this problem we need to keep track of where our median falls (i.e. in the required area where median is greater than or equal : y or in the "-1" rejected region where median ((n+1)/2) falls where it is less than y (and his mom would punish him).
so,to clarify more here's an example, he started by giving us k elements as follows :
k = 4 , n = 9 , y = 3;
1 3 4 5 , so here counter of elements greater than or equal to y (3) = 3 ,and lower (less than 3) equals 1 , what that means ? greater_Elements_counter + 1 > lower_Elements_counter ,which ensures that our median must falls in the area where : v [ (n+1) / 2] must be >= y , that the first part.
The second part comes as how to fill the remaining (n-k) elements in a way that we try to have out two conditions fulfilled (1 && 2 listed above). the idea is simple enough to follow : if our Greater_counter + 1 > lower_counter means we have condition 2 done and have to take care of condition 1 where sum < x , so minimize ? yes , put the smallest possible value : 1.
My code (tried to comment it as possible) : [submission:http://mirror.codeforces.com/contest/540/submission/13006828]
high Quality code : [submission:http://mirror.codeforces.com/contest/540/submission/10948313]
I tried my best , so of course anything unclear or wrong , please ask me to handle it ASAP. __
Thanks :).
