Easy approach...Similar to painters problem or book allocation approach


#1
#define ll long long

int getMax(vector<int> &arr, int n){
	int max = INT_MIN;
	for (int i = 0; i < n; i++)
		if (arr[i] > max)
			max = arr[i];
	return max;
}

int getmin(vector<int> &arr, int n){
	int total = INT_MAX;
	for (int i = 0; i < n; i++)
		total = min(arr[i],total);
	return total;
}

ll numberOfPainters(vector<int> &arr, int n, int maxlength) {
	ll sum = 0, numPainters = 1;
	for (int i = 0; i < n; i++) {
		if(arr[i] > maxlength)
		    sum += arr[i]-maxlength;
	}
	return sum;
}

int partition(vector<int> &arr, int k) {
	int n = arr.size();
	int low = getmin(arr,n);
	int high = getMax(arr, n);

	while (low < high) {
		ll mid = low + (high - low) / 2;

		ll required_painters = numberOfPainters(arr, n, mid);

		if (required_painters < k)
			high = mid;
		else
			low = mid + 1;
	}
	return low-1;
}

int Solution::solve(vector<int> &A, int B) {
    return partition(A,B);
}