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 vaccines 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
• N=5
• M= 2
arr= [7,4]
Approach
• There are 7 vaccines of pst 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.
Constraints
1<<N< 10^9
1<M < 100000
M<N
1 < arr[i] < 10^9
Sample Input
7 5
7 1 7 4 4
Output
4
Answers
Answer:
import java.util.*;
public class JealousyLevel {
public static void main(String[] args) {
// Input : N - no of dealers, M - Manufactured vaccines, arr - array of vaccines
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int arr[] = new int[m];
for(int i = 0; i < m; i++) {
arr[i] = sc.nextInt();
}
// Finding max
int max = 0;
for(int i = 0; i < m; i++) {
if(max < arr[i])
max = arr[i];
}
// First iteration
int iterationOfVaccine = 0;
int dealers[] = new int[n];
for(int i = 0; i < n; i++) {
if(iterationOfVaccine == m) {
iterationOfVaccine = 0;
}
dealers[i] = iterationOfVaccine;
iterationOfVaccine++;
}
int count = 0;
for(int i = 0; i < dealers.length; i++) {
if(dealers[i] == 0) {
count++;
}
}
System.out.println((max / count) + max % count);
}
}
Explanation:
Its not that much efficient but It'll work.
Answer:
#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 i = 0;i<t;i++){
int n;
cin >> n;
int m;
cin >> m;
vector<int> arr(m);
for(int j=0;j<m;j++){
cin >> arr[j];
}
int out;
out= solve(n, m, arr);
cout << out;
cout << "\n";
}
}
Explanation:
it's working all test cases passaunkanrki