PROBLEM LINK:
Author: Akash Kumar Bhagat
Tester: Sandeep Singh
Editorialist: Akash Kumar Bhagat
DIFFICULTY:
Easy- Med
PREREQUISITES:
Binary Search
PROBLEM:
You have N notebooks of different types numbered 1 to N with each books containing A_i number of pages respectively. Chefs Motive is to split these books into K separate notebooks having an equal number of pages.
No notebook can have pages from 2 or more different notebook type.
EXPLANATION:
This is a typical Binary Search Problem in which one has to maximize the number of pages in the new notebooks. Here it is possible to make K notebooks with fewer pages, like 1,2,3,4… pages in each new notebook. So one has to find the maximum number of pages on can fit in each book. To find this upper limit one can use Binary Search.
For example:
N=4 , K=11
A=[802,743,457,539]
PAGES: 1 2 3 4 5 ...... 198 199 200 201 202
POSSIBLE TO DISTRIBUTE(1/0) : 1 1 1 1 1 ...... 1 1 1 0 0
In this case, the answer will be 200 as this is the upper limit of the number of pages that one can split those N-type of notebooks to 11 kids.
TIME COMPLEXITY:
O(N*log n), where N is the types of notebook and n is the total search range.
SOLUTIONS:
Python 3.7
def chk(x):
temp=0
for i in a:
temp+=i//x
return temp>=k
for _ in range(int(input())):
n,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
l,r=0,max(a)+1
while(r>l+1):
mid=(l+r)//2
#print("*",mid,l,r)
if(chk(mid)):
l=mid
else:
r=mid
print(l)
CPP
#include <bits/stdc++.h>
#define ll long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ln cout << '\n'
#define mod 1000000007
#define MxN 100005
#define all(x) x.begin(), x.end()
using namespace std;
bool check(ll pages, int k, vector <ll>& books){
ll cnt = 0;
for(ll book : books){
cnt += book / pages;
if(cnt >= k)
return 1;
}
return 0;
}
void solve(){
int i, j, n, k;
ll sum = 0;
cin >> n >> k;
vector <ll> arr(n);
ll lft = 1, rgt = 0;
for(i = 0; i < n; ++i){
cin >> arr[i];
sum += arr[i];
rgt = max(rgt, arr[i]);
}
//rgt = max(rgt, sum / k);
rgt++;
while(lft < rgt){
ll mid = (lft + rgt ) / 2;
if(check(mid, k, arr))
lft = mid + 1;
else
rgt = mid;
}
cout << lft - 1 << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
int t = 1;
cin >> t;
while(t--)
solve();
}