题解 | #牛牛晾衣服#

题目的主要信息：

n件带水的衣服，含水量记录在数组a中，干燥的方式有两种：
自然晾干每分钟是晾干1滴水，烘干每分钟是烤干k滴水
每次烘干只能放入一件衣服，烘干与自然晾干同步进行，问最少多少分钟能将衣服全部干燥

方法一：二分法

具体做法：
按照题意，数组元素必有，且元素不为0，则一定有湿衣服，那么至少需要花费1分钟。
同时，如果所有的衣服都采用自然晾干，这是最慢的方式了，则至多会花费 $max(a_i)$ 分钟（当 $k=1$ 时也是这种情况）。
我们就可以采用二分法，探讨 $[1,max(a_i)]$ 中满足能够干燥全部衣服的最小值。找这个最小值，我们设置check函数，每次将两个边界的中值 $mid$ 放入探讨：遍历数组a，如果 $a[i]<=mid$ ，说明这个时间内它可以自然晾干，不需要烘干；如果 $a[i]>mid$ ，则我们需要使用烘干，当然烘干的时间不是整个 $a[i]$ 而是它超出来的部分，即 $a[i]>=time*k+(mid-time)$ ，公式前半部分是烘干，后半部分是自然晾干，因为多出来的部分还是要烘干，因此我们的 $time=(a[i]-mid)/(k-1)$ 需要向上取整，这里我们调用了ceil函数。如果总共需要的烘干时间大于了 $mid$ ，则无法在相应时间内弄干全部衣服，left扩大，否则right缩小，直到二者相遇。
图片说明

class Solution {
public:
    bool check(vector<int>& a, int mid, int k){
        int time = 0; //记录使用烘干的时间
        for(int i = 0; i < a.size(); i++){
            if(a[i] > mid) //mid时间内无法自然晾干，需要烘干
                time += ceil((double)(a[i] - mid) / (k - 1));
            if(time > mid) //总时间超过mid，不能完成
                return false;
        }
        return true;
    }
    int dryClothes(int n, vector<int>& a, int k) {
        int left = 1;
        int right = *max_element(a.begin(), a.end()); //找到最大值
        if(k == 1) //每分钟烘干1滴水时，直接返回最大
            return right;
        while(left < right){ //二分法
            int mid = (right + left) / 2; //取中间值
            if(check(a, mid, k))
                right = mid; //mid内能完成，尝试缩短时间
            else
                left = mid + 1; //mid内不能完成，尝试增加时间
        }
        return right;
    }
};

复杂度分析：

时间复杂度： $O(n*log_2max(a_i))$ ，二分法一共循环 $log_2max(a_i)$ 次，每次循环调用check函数一次，check函数复杂度为 $O(n)$
空间复杂度： $O(1)$ ，常数级空间使用

方法二：排序+二分查找优化

具体做法：
外面我们依然使用方法一的二分法验证 $[1,max(a_i)]$ 中的中值，但是我们可以先对整个数组a进行排序，那么我们在验证的时候就不用遍历数组a，而是可以用upper_bound函数二分查找到第一个大于mid的元素，然后往后遍历，省略了不少遍历的步骤，因为前面的元素都不会超过mid不影响最终的时间time。

class Solution {
public:
    bool check(vector<int>& a, int mid, int k){
        int time = 0; //记录使用烘干的时间
        auto iter = upper_bound(a.begin(), a.end(), mid); //二分查找，数组中第一个大于mid的数
        for(; iter != a.end(); iter++){
            if(*iter > mid) //mid时间内无法自然晾干，需要烘干
                time += ceil((double)(*iter - mid) / (k - 1));
            if(time > mid) //总时间超过mid，不能完成
                return false;
        }
        return true;
    }
    int dryClothes(int n, vector<int>& a, int k) {
        sort(a.begin(), a.end()); //排序
        int left = 1;
        int right = a[n - 1]; //找到最大值
        if(k == 1) //每分钟烘干1滴水时，直接返回最大
            return right;
        while(left < right){ //二分法
            int mid = (right + left) / 2; //取中间值
            if(check(a, mid, k))
                right = mid; //mid内能完成，尝试缩短时间
            else
                left = mid + 1; //mid内不能完成，尝试增加时间
        }
        return right;
    }
};

复杂度分析：

时间复杂度： $O(nlog_2n+n*log_2max(a_i))$ ，除去排序的复杂度 $O(nlog_2n)$ ，最坏情况下复杂度为： $log_2n+n/2+log_2n+3n/4+log_2n+7n/8+...=log_2n*log_2max(a_i)+n*log_2max(a_i)$ ，虽然check函数最坏复杂度没有变，但是因为去掉一些步骤，平均复杂度有所降低
空间复杂度： $O(1)$ ，无额外空间使用