1231. Divide Chocolate

LeetCode hard original: C# #array #csharp #hard #leetcode #search #two-pointers
Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.
LeetCode Static

У вас есть одна шоколадка, состоящая из нескольких кусочков. Каждый кусочек имеет свою сладость, заданную tableauом сладости. Вы хотите поделиться шоколадом со своими k друзьями, поэтому начинаете разрезать шоколадку на k + 1 кусочков с помощью k разрезов, каждый кусочек состоит из нескольких последовательных кусочков. Будучи щедрым, вы съедите кусочек с минимальной общей сладостью, а остальные кусочки отдадите своим друзьям. find максимальную общую сладость кусочка, который вы можете получить, оптимально разрезав шоколадку.

Exemple:

Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5

Output: 6

C# solution

correspondant/original 
public class Solution {
    public int MaximizeSweetness(int[] sweetness, int k) {
        bool CanDivide(int minSweetness) {
            int currentSum = 0, cuts = 0;
            foreach (var sweet in sweetness) {
                currentSum += sweet;
                if (currentSum >= minSweetness) {
                    cuts++;
                    currentSum = 0;
                }
            }
            return cuts >= k + 1;
        }
        
        int left = sweetness.Min();
        int right = sweetness.Sum() / (k + 1);
        
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (CanDivide(mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
}

C++ solution

brouillon automatique, à relire avant soumission 
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaximizeSweetness(vector<int>& sweetness, int k) {
        bool CanDivide(int minSweetness) {
            int currentSum = 0, cuts = 0;
            foreach (var sweet in sweetness) {
                currentSum += sweet;
                if (currentSum >= minSweetness) {
                    cuts++;
                    currentSum = 0;
                }
            }
            return cuts >= k + 1;
        }
        
        int left = sweetness.Min();
        int right = sweetness.Sum() / (k + 1);
        
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (CanDivide(mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
}

Java solution

correspondant/original 
public class Solution {
    public int maximizeSweetness(int[] sweetness, int k) {
        int left = Arrays.stream(sweetness).min().getAsInt();
        int right = Arrays.stream(sweetness).sum() / (k + 1);

        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (canDivide(sweetness, k, mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

    private boolean canDivide(int[] sweetness, int k, int minSweetness) {
        int currentSum = 0, cuts = 0;
        for (int sweet : sweetness) {
            currentSum += sweet;
            if (currentSum >= minSweetness) {
                cuts++;
                currentSum = 0;
            }
        }
        return cuts >= k + 1;
    }
}

Python solution

correspondant/original 
def maximizeSweetness(sweetness, k):
    def canDivide(minSweetness):
        current_sum = 0
        cuts = 0
        for sweet in sweetness:
            current_sum += sweet
            if current_sum >= minSweetness:
                cuts += 1
                current_sum = 0
        return cuts >= k + 1

    left, right = min(sweetness), sum(sweetness) // (k + 1)
    while left < right:
        mid = (left + right + 1) // 2
        if canDivide(mid):
            left = mid
        else:
            right = mid - 1
    return left

Go solution

correspondant/original 
func maximizeSweetness(sweetness []int, k int) int {
    canDivide := func(minSweetness int) bool {
        currentSum, cuts := 0, 0
        for _, sweet := range sweetness {
            currentSum += sweet
            if currentSum >= minSweetness {
                cuts++
                currentSum = 0
            }
        }
        return cuts >= k + 1
    }
    
    left, right := sweetness[0], 0
    for _, sweet := range sweetness {
        if sweet < left {
            left = sweet
        }
        right += sweet
    }
    right /= k + 1
    
    for left < right {
        mid := (left + right + 1) / 2
        if canDivide(mid) {
            left = mid
        } else {
            right = mid - 1
        }
    }
    
    return left
}

Algorithm

Для решения задачи мы можем использовать метод двоичного поиска для определения максимальной минимальной сладости, которую можно получить.

Двоичный поиск:

Мы будем искать ответ в диапазоне от минимальной сладости до суммы всех сладостей. Начнем с середины этого диапазона и проверим, можно ли разрезать шоколад таким образом, чтобы минимальная сладость была не менее этого значения.

Проверка делимости:

Для каждой попытки значения сладости в двоичном поиске проверим, можем ли мы разрезать шоколад так, чтобы каждая из k+1 частей имела сладость не меньше текущего значения.

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres
Il n'y a pas encore d'offres actives.