Editorial for GlobeX Cup '18 S2 - Test Scores
Submitting an official solution before solving the problem yourself is a bannable offence.
We can observe that in order to obtain an average of at least ~K~, your test scores need to add up to a value of at least ~N \times K~. Thus, in the solution, we can keep adding on to this total score until ~N \times K~ is reached.
For the first subtask, we add 1 to the total score each time. We can decide the test score we should add to by iterating through all of the test scores that are below ~M~ and finding the test with the lowest ~y_i~ value. We can then add 1 to that test score.
For the second subtask, we also add 1 to the total score each time. Instead of looping through all the tests this time, we can use a data structure such as a priority queue to help us find the lowest ~y_i~ value faster.
For the third subtask, we can store two values for each test in an array: ~M - x_i~, and ~y_i~. The first value represents the number of points we can increase this test by until it reaches M. The second represents the number of hours you need to study to increase the score by 1 point. Then, we can sort the array to form an array with non-decreasing ~y_i~ values. Then, we traverse the array and keep increasing the total score by ~M - x_i~ until it exceeds ~N \times K~. Finally, we subtract the extra hours that we studied to lower the total score to ~N \times K~.