1231. 分享巧克力

你有一大块巧克力，它由一些甜度不完全相同的小块组成。我们用数组 sweetness 来表示每一小块的甜度。
你打算和 K 名朋友一起分享这块巧克力，所以你需要将切割 K 次才能得到 K+1 块，每一块都由一些 连续 的小块组成。
为了表现出你的慷慨，你将会吃掉 总甜度最小 的一块，并将其余几块分给你的朋友们。
请找出一个最佳的切割策略，使得你所分得的巧克力 总甜度最大，并返回这个 最大总甜度。

class Solution {
public:
    int calccount(vector<int> &sweetness, int sweet)
    {
        int sum = 0;
        int count = 0;
        for (auto &i : sweetness) {
            sum += i;
            if (sum >= sweet) {
                count++;
                sum = 0;
            }
        }

        return count;
    }


    int maximizeSweetness(vector<int> &sweetness, int K)
    {

        int sum = 0;
        int minvalue = INT32_MAX;
        for (auto &i : sweetness) {
            sum += i;
            minvalue = min(minvalue, i);
        }

        if (K == 0) {
            return sum;
        }

        int left = minvalue;
        int right = sum;
        while (left < right) {
            int mid = left + (right - left+1) / 2;

            int count = calccount(sweetness, mid);
            if (K + 1 <= count) {
                left = mid;

            } else {
                right = mid - 1;
            }
        }

        return left;
    }
};

对于一个固定分割大小的巧克力块，分割时最小甜度值的下限为单各单元的巧克力的甜度值，不可达上限是所有巧克力的甜度值之和。

二分查找的目标是找到满足分割条件的最大最小甜度值，即对每个二分的甜度值用巧克力块分割进行验证，判断能否完成K次分割，如果不行说明最小甜度值过大，否则最小甜度值过小。