Vaccine Distribution

 Coding Problem Keys 

 Vaccine Distribution 

 Problem Statement 

There is a large manufacturer of vaccine which produces M types of vaccines (whose formulas are derived from different pharma brands). The manufacturer needs to divide all the vaccines between N dealers. It is acceptable if some dealers do not get any vaccine. However, no dealer wants vaccine of different kinds which means that all vaccines that a dealer gets need to be of the same type.

The manufacturer also knows that dealers will be jealous if a dealer gets too many vaccines. As an approximation, the jealousy level among the dealers is defined as the largest number of vaccines given to any dealer.

 Task 

Help the manufacturer to divide all the vaccines among the dealers such that the jealousy level is minimized.

 Example 

Assumptions

• N = 5
• M = 2
• arr = [7, 4]

 Approach 

• There are 7 vaccines of 1st type and 4 vaccines of 2nd type. Let the two types be defined by P and Q.
• So, if the manufacturer divides the vaccines as PP, PP, PPP, QQ, QQ. This will be optimal distribution.
• Thus, the answer is 3.

 Function Description 

Complete the function solve provided in the editor. This function takes the following 3 parameters and returns the minimum possible jealousy level.

• N: Represents the number of dealers.
• M: Represents the number of types of vaccines.
• arr: Represents the array of M integers where arrᵢ represents the number of vaccines of type i. 

 Input Format 

 Note 

This is the input format that you must use to provide custom input.

• The first line contains T denoting the number of test cases. T also specifies the number of times that you have to run the solve function on a different set of inputs.
• For each test case:
• The first line of input contains two positive integers N and M.
• The next line contains M space-separated positive integers, with the Kth integer denoting the number of vaccines of type K.

 Output Format 

For each test case, print the minimum possible jealousy level in a new line.

 Constraints 

1 ≤ T ≤ 10

1 ≤ N ≤ 10⁹

1 ≤ M ≤ 100000

M ≤ N

1 ≤ arr[i] ≤ 10⁹

 Sample Test Case 

 Sample Input 1 

1

7 5

7 1 7 4 4

 Sample Output 1 

4

 Explanation 

The first line contains the number of test cases, T = 1.

 The first test case 

 Given 

• N = 7
• M = 5
• arr = [7, 1, 7, 4, 4]

 Approach 

Following is the optimal distribution of vaccines:

• Dealer 1: 4 vaccines of type 1
• Dealer 2: 3 vaccines of type 1
• Dealer 3: 1 vaccine of type 2
• Dealer 4: 3 vaccines of type 3
• Dealer 5: 4 vaccines of type 3
• Dealer 6: 4 vaccines of type 4
• Dealer 7: 4 vaccines of type 5

Thus, the answer is 4.

 Time Limit:  10 sec(s) for each input file

 Memory Limit:  256 MB

 Source Limit:  1024 KB

 Solution 

 Programming Language: C++ Language 

#include <bits/stdc++.h>
using namespace std;
int solve(int N, int M, vector<int> arr) {
    long long l=1,r=*max_element(arr.begin(),arr.end()),mid,cnt;
    while(l<r) {
        mid=(l+r)/2;
        cnt=0;
        for(auto & i:arr) cnt+=ceil(1.0*i/mid);
        if(cnt>N) l=mid+1;
        else r=mid;
    }
    return l;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for(int t_i =0; t_i < T; t_i++){
        int N;
        cin >> N;
        int M;
        cin >> M;
        vector<int> arr(M);
        for(int i_arr=0; i_arr<M;i_arr++){
            cin>>arr[i_arr];
        }
        int out_;
        out_=solve(N,M,arr);
        cout<<out_;
        cout<<"\n";
    }
}

// Published By PKJCODERS

 (Note: Incase If the code doesn't Pass the output kindly comment us with your feedback to help us improvise.)