Can someone help me with this problem -
There is a school in a village. It has N classes. One fine day, someone donated B blue berry cheese cakes to schools. Now you need to divide these cakes such that:
Each class gets at least 1 cake.
Each class will share the cake(s) among students.
Your aim is to minimize the maximum number of students per cake in any class.
Input
The first line of the input contains two space separated integers N and B denoting the number of classes and total number of blue berry cheese cakes, respectively.
Next N lines contain number of students in each class.
Output
For each test case, output the maximum number of students who will share a cake.
Constraints
2 <= N <= 5105 N <= B <= 2106 1 <= number of students in ith class <= 5*106
Sample Input 1 2 35
Sample Output 18
Sample Input 2 7 20 50
Sample Output - 2 10
what would be answer for
8 17
3 5 2 6 5 10 7 4
my answer is 3
You can approach this question with binary search.
Binary search on the maximum number of students who will share the cake as follows:
-set lower_limit as 1 and upper_limit as the maximum student in any class
-calculate mid=(lower_limit+upper_limit)/2
-calculate the number of cakes required if mid is the "maximum number of students per cake"
-if this count is more than available cakes(b) then increase lower_limit otherwise decrease upper_limit
One corner case is when the number of cakes is less than the number of classes.Handle it separately.
Link to my C++ code for this problem :
1 Like
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll clas[10000];
ll ciel(float a)
{
ll t=a;
if(t!=a)
t++;
return t;
}
int main()
{
ios::sync_with_stdio(0);
ll n,b;
cin>>n>>b;
ll l=1,r=0;
for(int i=0;i<n;i++)
{
cin>>clas[i];
r=max(r,clas[i]);
}
if(b<n)//number of cakes is less than number of classes
{
cout<<"-1";
return 0;
}
//binary search on "maximum number of students " who will share a cake
while(l<r)
{
ll mid=(l+r)/2;
ll cakes_req=0;
for(int i=0;i<n;i++)
{
cakes_req+=ciel((clas[i]/(float)mid));
}
if(cakes_req<=b)
{
r=mid;
}
else
{
l=mid+1;
}
}
cout<<r;
}