Join UsSite Message
Only Premium Users can view the Question
Entering edit mode
#include<bits/stdc++.h>
using namespace std;
int check(int n, vector<int> hash, int x){
if(n==0){
return 1;
}
sort(hash.begin(),hash.end());
for(int i=0;i<x;i++){
if(hash.empty()){
return 0;
}
if(hash.back()>=n){
hash.pop_back();
}
else{
int temp=hash.back();
hash.pop_back();
if(hash.empty()){
return 0;
}
hash.back()+=temp;
i--;
}
}
return 1;
}
int main(){
int n,x;
cin>>n>>x;
vector<int> arr(n);
int count=0;
for(int i=0;i<n;i++){
cin>>arr[i];
count+=arr[i];
}
int mini=0;
int maxi= ceil(count/x);
while(mini<=maxi){
int mid=(mini+maxi)/2;
if(check(mid,arr,x)){
mini=mid+1;
}
else{
maxi=mid-1;
//solutions at maxi;
}
}
cout<<maxi<<endl;
return 0;
}
