To divide an array into k segments such that the minimum of the segments is the maximum

general
, , , , ,
1

Given an array of n elements divide the elements into k segments such that the minimum sum of each of the segments is maximum

eg

array is
10 5 8 7

and k is 2

the different ways to divide the array into two segment is

(10) , (5,8,7) min sum is 10

(10,5) (8,7) min sum is 15

(10,5,8) (7) min sum is 7

so the max of the minimum is 15 (7<10<15)

1< n , k < 10^5

how to attain the solution in O(n) or O(nlog n )

1 Like
2

this can be done using binary search+greedy

Here link is a similar question and my solution link

comment if you have any doubt.

1 Like
3

I hope this isnt related to an on going contest.

4

can you please explain your logic behind the code? Came across a similar problem, so would be of great help if you could.

5

#include<bits/stdc++.h>
using namespace std;
bool isPossible(int mid, int k, vector&arr){

int sum=0,cnt=0;
for(int i=0;i<(int)arr.size();i++){
     sum+=arr[i];
     if(sum>=mid){
        cnt++;
        sum=0;
     }
}
return cnt>=k;

}
int main(){
int n,k;
cin>>n>>k;
vectorarr(n);
for(int i=0;i<n;i++)cin>>arr[i];
int l=0,h=0,ans=0;
for(int i:arr)h+=i;
while(h>=l){
int mid=(l+h)/2;
if(isPossible(mid, k, arr)){
ans =mid;
l=mid+1;
}
else h=mid-1;
}
cout<<ans<<endl;
}