2

Maximize minimum sweetness in cake cutting

 1 year ago
source link: https://www.geeksforgeeks.org/maximize-minimum-sweetness-in-cake-cutting/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Maximize minimum sweetness in cake cutting

shivammiglani09

Given that cake consists of N chunks, whose individual sweetness is represented by the sweetness[] array, the task is to cut the cake into K + 1 pieces to maximize the minimum sweetness.

Examples:

Input: N  = 6, K = 2, sweetness[] = {6, 3, 2, 8, 7, 5}
Output: 9
Explanation: Divide the cake into [6, 3], [2, 8], [7, 5] with sweetness levels 9, 10, and 12 respectively.

Input: N  = 7, K = 3, sweetness[] = {1, 2, 4, 7, 3, 6, 9}
Output: 7
Explanation: Divide the cake into [1, 2, 4], [7], [3, 6], [9]  with sweetness levels 7, 7, 9, and 9 respectively.

Approach: This can be solved with the following idea:

The approach used is the binary search to find the maximum sweetness value that can be achieved after dividing the given array of sweetness values into k + 1 groups, where each group has a minimum sweetness value of mn_value.

Steps involved in the implementation of code:

  • First, we initialize the variables “sum” and “mn_value” to calculate the sum of all sweetness levels and the minimum sweetness level in the array respectively.
  • We set the low and high values of binary search as 1 and sum respectively.
  • We perform a binary search on the range [low, high] until low > high. In each iteration, we calculate the mid-value and call the “canSplit” function to check if the array can be split into k+1 subarrays where the minimum sweetness level of each subarray is at least mid.
  • If “canSplit” returns true, we store the current mid value as the answer and update the low value to mid+1 to search for larger mid values.
  • Otherwise, if “canSplit” returns false, we set the high value to mid-1 to search for smaller mid-values.
  • Finally, we return the answer.

Below is the implementation of the above approach:

// Java Implementation
public class Main {
// Function to check whether split is
// possible
public static boolean canSplit(int[] sweetness,
int mn_value, int k)
{
int curr = 0;
int cnt = 0;
for (int i = 0; i < sweetness.length; i++) {
curr += sweetness[i];
if (curr >= mn_value) {
cnt++;
curr = 0;
}
}
return cnt >= k + 1;
}
// Function to maximize the
// minimum sweetness
public static int maxSweetness(int[] sweetness, int n,
int k)
{
int sum = 0;
int mn_value = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
sum += sweetness[i];
mn_value = Math.min(mn_value, sweetness[i]);
}
int low = 1;
int high = sum;
int ans = 0;
while (low <= high) {
int mid = (low + high) / 2;
// If split is possible
if (canSplit(sweetness, mid, k)) {
ans = mid;
low = mid + 1;
}
else {
high = mid - 1;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int[] sweetness = { 6, 3, 2, 8, 7, 5 };
int n = sweetness.length;
int k = 2;
// Function call
int result = maxSweetness(sweetness, n, k);
System.out.println(result);
}
}
Output
9

Time Complexity: O(n * log(sum))
Auxiliary Space:  O(1)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK