题解 | #牛牛晾衣服#

题目：
牛牛有n件带水的衣服，干燥衣服有两种方式。
一、是用机器烘干，可以每分钟烤干衣服的k滴水。
二、是自然烘干，每分钟衣服会自然烘干1滴水。
机器比较小，每次只能放进一件衣服。
注意，使用机器的时候，其他衣服仍然可以保持自然烘干状态，现在牛牛想知道最少要多少时间可以把衣服全烘干。

方法一：暴力查找
所需的最短烘干时间为1，最长时间为a[i]最大值，则在1到max(a[i])中直接暴力寻找可行的最短烘干时间

那么我们需要一个函数判断衣服是否可以被烘干：
如果衣服的水滴数小于总的烘干时间time，那么这件衣服一定会被烘干，所以凡是衣服水滴数大于总烘干时间则需要进行计算，总烘干时间为time,设需要机器烘干的时间为t，则机器烘干的水滴数为 $t*k$ ,自然烘干的水滴数为 $time-k$ ,则 $t*k+time-k<=a[i]$ ,即 $t<=(a[i]-time)/(k-1)$ ,累计需要机器烘干的时间，如果时间大于总的烘干时间则说明该时间内无法烘干所有衣服，否则可以烘干.
例如有3件衣服，水滴数量为[2,3,9],机器每分钟烘干水滴数量为5，则在1到9之间寻找最短的可行时间，当 $time=1，a[0]>time,drytime=1,a[1]>time,drytime=1+1,a[2]>time,drytime=1+1+2=4>1$ ,则在1分钟内无法烘干衣服，继续延长时间为 $time=2,a[0]=time$ ，可以自然烘干， $a[1]>time,drytime=1,a[2]>time,drytime=1+2=3>2$ ,则2分钟内也无法烘干衣服， $time=3,a[0]<time,a[1]=time$ ,自然烘干， $a[2]>time,drytime=2<3$ ,则在3分钟内可以烘干所有衣服，返回结果

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最少要多少时间可以把所有的衣服全烘干
     * @param n int整型 n件衣服
     * @param a int整型一维数组 n件衣服所含水量数组
     * @param k int整型 烘***1分钟可以烘干的水量
     * @return int整型
     */
    public int dryClothes (int n, int[] a, int k) {
        // write code here
        int max=0;
        //假设全部自然烘干，找到水滴数最多的衣服即为最长烘干时间
        int i;
        for(i=0;i<n;i++){
            max=Math.max(max,a[i]);
        }
        for(i=1;i<=max;i++){//寻找1到max时间内最短烘干时间
            if(isdry(i,a,k))break;
        }
        return i;
    }
    boolean isdry(int time,int[]a,int k){
        int drytime=0;//机器烘干时间
        for(int i=0;i<a.length;i++){
            if(a[i]>time){//只有水滴数大于烘干时间的才用机器
                if((a[i]-time)%(k-1)==0)
                    drytime+=(a[i]-time)/(k-1);
                else drytime+=(a[i]-time)/(k-1)+1;
            }
            if(drytime>time)return false;
        }
        return true;
    }
}

复杂度：
时间复杂度： $O(max(a[i])*n)$ ,外层循环不超过 $max(a[i])$ ,isdry()函数的复杂度不超过 $O(n)$

空间复杂度： $O(1)$ ,额外变量的复杂度为常数级
方法二：二分查找
暴力查找时间复杂度过高，我们可以使用二分查找寻找最短的可行时间，所需的最短烘干时间为1，最长时间为a[i]最大值，即假设水滴数最多的衣服自然烘干，则其时间最长，在1到max(a[i])中二分查找可以烘干衣服的最短时间，如果在mid时间内衣服可以烘干，则缩短时间往左区间查找，寻找是否存在更短的可行时间，否则延长时间往右区间查找

图片说明

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最少要多少时间可以把所有的衣服全烘干
     * @param n int整型 n件衣服
     * @param a int整型一维数组 n件衣服所含水量数组
     * @param k int整型 烘***1分钟可以烘干的水量
     * @return int整型
     */
    public int dryClothes (int n, int[] a, int k) {
        // write code here
        int max=0;
        for(int i=0;i<n;i++){
            max=Math.max(max,a[i]);//假设水滴数量最多的衣服自然烘干，则最长烘干时间不超过这个值

        }
        int l=1,r=max;
        while(l<=r){//在1和最长烘干时间内寻找最短烘干时间
            int mid=l+(r-l)/2;
            if(isdry(mid,a,k)) r=mid-1;//能烘干再尝试更短的时间
            else l=mid+1;//不能烘干则时间延长
        }

        return l;
    }
    boolean isdry(int time,int[]a,int k){
        int drytime=0;//使用机器烘干的时间
        for(int i=0;i<a.length;i++){
            if(a[i]>time){//如果第i件衣服不能自然烘干，则假设它使用机器烘干
                if((a[i]-time)%(k-1)==0)
                    drytime+=(a[i]-time)/(k-1);
                else drytime+=(a[i]-time)/(k-1)+1;//向上取整
            }
            if(drytime>time)return false;
        }
        return true;
    }
}

复杂度：
时间复杂度： $图片说明$ ,二分查找的时间 $图片说明$ ,而isdry()函数的复杂度不超过 $O(n)$
空间复杂度： $O(1)$ ,额外变量的复杂度为常数级