题目的主要信息：

烘干机可以每分钟烤干k滴水，自然烘干每分钟烘干1滴水；使用烘干机的时候可以同时进行自然烘干；
已经烘干机每分钟烤干水滴数和需要烘干的衣服的数量和水滴数，求解需要多长时间将所有衣服晾干。

方法一：暴力枚举法

最长的时间是所有衣服全部自然晾干需要的时间，即a数组中最多水滴数的为最大时间max。由于每件衣服都是湿的，所以所需时间至少为1，遍历一遍1到max的时间，判断是否能晾干所有衣服，若能晾干则是最小的时间。

具体做法：

class Solution {
public:
    bool isAvailable(int time,vector<int>& a, int k){//判断在time时间里，能否把所有衣服弄干
        int t = 0;//把所有衣服晾干需要使用多少分钟的烘干机
        for(int i = 0;i < a.size();i++)
        {
            if(a[i] > time)
            {
                t+=ceil((double)(a[i]-time)/(k-1));//计算把a[i]晾干需要使用烘干机的分钟数
            }
            if(t > time) return false;//使用烘干机的时间超过了time，那么就不可能在time时间内晾干所有衣服
        }
        return true;//可以在time时间内晾干所有衣服
    }
    
    int dryClothes(int n, vector<int>& a, int k) {
        sort(a.begin(),a.end());//对a进行排序
        int left = 1;//因为有衣服是湿的，left=1是最小的晾干时间，
        int max = a[a.size()-1];//right是最大的晾干时间
        if(k==1)//如果每分钟烘干的水滴数为1就相当于全程晒干
        {
            return max;
        }
        int i=0;
        for(i=1;i<max;i++)//枚举所有可能
        {
            if(isAvailable(i, a, k)){//判断是否可行
                break;
            }
        }
        return i;
    }
};

复杂度分析：

时间复杂度： $O (n^{2})$ ，最坏情况下需要遍历所有的可能时间，每一次遍历都需要遍历一遍数组。
空间复杂度： $O (1)$ ，只使用了常数空间。

方法二：二分法枚举

枚举时间t，判断在时间t内能否把所有衣服晾干。分为两种情况：

所有的衣服都能在t内晾干，不需要使用烘干机。
有衣服需要使用烘干机。假设使用烘干机的时间为m，衣服的水滴数为a，自然晾干的水滴数为t-m，则需要满足t-m+km >= a。得到 m >= (a-t)/(k-1)。如果m>t，说明在t时间内不能把衣服晾干。

为了减少枚举的时间，首先对a进行排序，找到中间的数字开始枚举，接着使用二分法的思想继续枚举，如果时间t太小，则增大t的范围值，如果t太大，则缩小t的范围值。

alt

具体做法：

class Solution {
public:
    bool isAvailable(int time,vector<int>& a, int k){//判断在time时间里，能否把所有衣服弄干
        int t = 0;//把所有衣服晾干需要使用多少分钟的烘干机
        for(int i = 0;i < a.size();i++)
        {
            if(a[i] > time)
            {
                t+=ceil((double)(a[i]-time)/(k-1));//计算把a[i]晾干需要使用烘干机的分钟数
            }
            if(t > time) return false;//使用烘干机的时间超过了time，那么就不可能在time时间内晾干所有衣服
        }
        return true;//可以在time时间内晾干所有衣服
    }
    int dryClothes(int n, vector<int>& a, int k) {
        // write code here
        sort(a.begin(),a.end());//对a进行排序
        int left = 1;//因为有衣服是湿的，left=1是最小的晾干时间，
        int right = a[a.size()-1];//right是最大的晾干时间
        if(k==1)//如果每分钟烘干的水滴数为1就相当于全程晒干
        {
            return right;
        }
        while(left < right)
        {
            int mid = (left + right)/2;//找到中间值
            if(isAvailable(mid,a,k))//判断mid时间是否能晾干所有衣服
            {
                right = mid;//如果可以的话，缩小mid的值
            }else{
                left = mid + 1;//如果不可以，增大mid的值
            }
        }
        return left;
    }
};

复杂度分析：

时间复杂度： $O (n l o g_{2} n)$ ，二分法的时间为 $O (l o n g_{2} n)$ ，每次调用isAvailable需要 $O (n)$ 复杂度。
空间复杂度： $O (1)$ ，只使用了常数空间。

题解 | #牛牛晾衣服#

题目的主要信息：

方法一：暴力枚举法

方法二：二分法枚举