题解 | #牛牛晾衣服#

题意整理

给定n件带水的衣服，用一个数组记录每个衣服的水滴数。
现在要将所有衣服烘干，有两种方式，一种是自然烘干，每件衣服减少一滴水；另一种是机器烘干，其中一件衣服减少k滴水，剩下的衣服减少一滴水（自然烘干）。
求最少花多长时间将所有衣服烘干。

方法一（枚举）

1.解题思路

首先确定花费时间的左右边界，n大于等于1，说明至少有一件衣服待烘干，至少花费1分钟，左边界为1。如果所有衣服均自然烘干，花费时间最长，此时水滴最多的衣服即是总花费时间，对应右边界。
然后判断某个时间time内，是否能烘干所有衣服，如果a数组内衣服水滴数小于等于time，说明能自然烘干，所以只需考虑大于time的情况。如果某件衣服水滴数大于time，假设其机器烘烤时间为t,则自然烘烤时间为time-t，对应烘干的水滴数为 $t*k+time-t$ ，这个水滴数必须大于等于 $a[i]$ ，对应的衣服才能在time时间内烘干，所以有 $t*k+time-t>=a[i]$ ，整理得： $t>=(a[i]-time)/(k-1)$ ，所以每件衣服得机器烘干时间至少为t。将所有机器烘干时间累加，如果小于等于time，说明time时间是可行的。

2.代码实现

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) {
        //求最大值
        int max=-1;
        for(int i=0;i<n;i++){
            max=Math.max(max,a[i]);
        }
        //花费时间在1到max之间
        for(int i=1;i<=max;i++){
            //看i时间内，是否能烘干所有衣服
            if(check(i,a,k)){
                return i;
            }
        }
        return -1;
    }

    //time是用于烘烤的总时间花费
    private boolean check(int time,int[] a,int k){
        //烘***用时
        int dryTime=0;
        for(int i=0;i<a.length;i++){
            //取大于等于(a[i]-time)/(k-1)的时间花费
            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;
                }
            }
            //只要大于总时间花费，说明time时间内不能烘干所有衣服
            if(dryTime>time){
                return false;
            }
        }
        return true;
    }
}

3.复杂度分析

时间复杂度：check函数的时间复杂度为 $O(n)$ ，假设a数组最大值为max，最坏情况下，需执行max次check函数，所以时间复杂度为 $O(max*n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。

方法二（二分查找）

1.解题思路

确定左右边界以及检查time时间是否可行的思路和方法一相同。
然后查找的时候，可以考虑二分查找，因为从l到r是单调递增的，如果某个time可行，则大于等于time的时间也一定可行，只需确定可行域的左边界，即可找到最少的时间花费。

动图展示：
图片说明

2.代码实现

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) {
        //求最大值
        int max=-1;
        for(int i=0;i<n;i++){
            max=Math.max(max,a[i]);
        }
        //确定左右边界
        int l=1;
        int r=max;
        //二分，取可行域的左边界
        while(l<r){
            int mid=l+(r-l)/2;
            //如果满足条件，缩小可行域
            if(check(mid,a,k)){
                r=mid;
            }
            //不满足，排除左边所有数值
            else{
                l=mid+1;
            }
        }
        return l;
    }

    //time是用于烘烤的总时间花费
    private boolean check(int time,int[] a,int k){
        //烘***用时
        int dryTime=0;
        for(int i=0;i<a.length;i++){
            //取大于等于(a[i]-time)/(k-1)的时间花费
            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;
                }
            }
            //只要大于总时间花费，说明time时间内不能烘干所有衣服
            if(dryTime>time){
                return false;
            }
        }
        return true;
    }
}

3.复杂度分析

时间复杂度：check函数的时间复杂度为 $O(n)$ ，假设a数组最大值为max，需执行 $log_2(max)$ 次check函数，所以时间复杂度为 $O(n*log_2(max))$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。