Problem Link:
Contest
Practice
Author: Rajat De
Editorialist: Sidhant Bansal
Difficulty: Easy
Pre-requisites: Sorting
Quick Explanation:
Sort all the subjects in descending order according to C[i] and then greedily spend the hours on each of the subject turn by turn till the time the average does not come upto M.
Explanation:
For the average to be at least M, the total of all the marks should be at least M*N
If \sum A[i] \geq M*N then answer is 0.
Otherwise, calculate delta = (M*N) - \sum A[i]
Now, the original question reduces to studying least amount of hours so as to gain delta marks.
For calculating this, follow the below pseudocode -
Sort all subjects in descending order according to C[i]
Set answer = 0
For i = 1 to N
If B[i] - A[i] \geq delta
answer = answer + ceil(delta/C[i])
break
Else
answer = answer + (B[i] - A[i])/C[i]
delta = delta - (B[i] - A[i])
Print answer
Complexity: Time complexity is O(N * logN) and memory complexity is O(N)
The alternate solution is binary search on answer along with min cost max flow, please refer to the author solution for more details.