Last Updated: 25 Jan, 2021
Battalions and tanks
Moderate
Asked in companies
Let there be ‘N’ battalions of soldiers and ‘M’ tanks. You are also given an array/list of length ‘N’ whose i-th index denotes the number of soldiers in the i-th battalion. You are supposed to divide the ‘M’ tanks to ‘N’ battalions such that the maximum ratio of soldiers in a battalion to the number of tanks allotted to that battalion is minimised.
You can assume that the number of tanks is always greater than the number of battalions.
Input Format :
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first input line of each test case contains two integers ‘N’ and ‘M’ denoting the number of battalions and tanks respectively.
The second line of each test case contains ‘N’ space-separated integers denoting the number of soldiers in ‘N’ battalions.
Output Format :
For each test case, return the maximum ratio of soldiers in a battalion to the number of tanks as described in the problem statement.
Your answer is considered correct if its absolute or relative error doesn't exceed 0.000001.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 50
1 <= ‘N’ <= 1000
‘N’ <= ‘M’ <= 10000
1 <= ARR[i] <= 1000000
Time limit: 1 sec
Approaches
Let us first assign 1 tank to each battalion because the number of tanks assigned to any battalion will definitely be greater than or equal to 1. Now, if any extra tank is left then assigning the tank to the battalion having the maximum ratio of soldiers to the number of tanks will be an optimal choice. Because the maximum ratio will definitely decrease if we assign the next tank to this battalion. Similarly, we can do it for each remaining tank.
We can observe here that at each instance we are supposed to find the battalion having the maximum ratio. We can easily perform this task using a max-heap.
Consider the following steps:
- Let us create a max-heap of pair<int, int> where the first integer denotes the number of soldiers in the battalion and the second integer denotes the number of tanks assigned to that battalion. We will have to write a custom comparator for this max-heap such that the battalion with the maximum ratio is always at the top.
- Now, let us assign a tank to each battalion and insert the pair of index and tank in the max-heap. And decrement the count of remaining tanks i.e. ‘M’ = ‘M’ - ‘N’
- Now, for each remaining tank:
- Get the top-most element of max-heap which will be the battalion with the maximum ratio.
- Assign the current tank to this battalion i.e. increment the count of tanks allotted.
- Insert the updated battalion information in the max-heap.
- Get the top-most element of max-heap which will be the battalion with the maximum ratio.
The basic idea of this approach is to find the minimum ratio using a binary search.
Let us see how to check if a given real number (say ‘X’) is the minimum ratio(as defined in the problem statement) or not.
We will iterate through each battalion and allot a minimum number of tanks to each battalion such that the ratio of the number of soldiers to the number of tanks allotted is less than or equal to ‘X’. Now, if the sum of total allotted tanks exceeds the number of tanks given then, the minimum ratio must be greater than the chosen ‘X’. Otherwise, the minimum ratio will be either ‘X’ or less than ‘X’.
Consider the following steps:
- Initialize the search space for the minimum ratio . ‘l’ = 0.0 and ‘r’ = 10^6. Maximum possible value can be estimated by the maximum possible number of soldiers in any battalion.
- Now, loop until (r - l) > 0.000001. Because it is given that the answer will be correct if the absolute error is less than or equal to 0.000001.
- Assign ‘MID’ = l + (r - l)/2.0
- Now, initialize a variable ‘COUNT’ to zero which stores the ‘COUNT’ of tanks allotted to all the battalions.
- Iterate through the battalions and allot a minimum number of tanks to each battalion such that the ratio of the number of soldiers to the number of tanks allotted is less than equal to the 'MID'. Also add the number of allotted tanks to ‘COUNT’.
- Now, if ‘COUNT’ > ‘M’ then, update the ‘l’ to 'MID'. Because the minimum ratio will be definitely greater than 'MID'.
- Otherwise, update the ‘r’ to 'MID'. Because the minimum ratio will be definitely less than or equal to 'MID'.
Similar problems