【牛客编程巅峰赛S1第3场】牛牛晾衣服

题目

有 n 件带水的衣服，干燥衣服有两种方式。
一、是用烘***，可以每分钟烤干衣服的 k 滴水。
二、是自然烘干，每分钟衣服会自然烘干 1 滴水。
烘***比较小，每次只能放进一件衣服。
注意，使用烘***的时候，其他衣服仍然可以保持自然烘干状态，求可以把衣服全烘干的最少时间。

解题思路

使用二分法：

1. 先确定上下限：所求时间最少是 1 分钟；最多时间是数组 中的最大值，此时所有衣服自然烘干。
2. 取上下限的中间值，调用 函数判断所有衣服是否能在 时间内烘干，根据判断结果更新时间上下限，并更新满足题意的最少时间。

函数 的作用是判断序列 中的所有衣服是否能在 分钟内完全烘干。判断方法是：烘***使用时间如果大于 ，返回 ；否则返回 。

• 如果 ，表示在 时间内完全可以自然烘干，不需要占用烘***的时间。
• 如果 ，不能在 时间内完全自然烘干。如果想让它在 时间内烘干，就需要使用烘***。
  这个烘***使用时间 的计算如下：
  机器烘干的水滴数为 ，自然烘干时间为 ，自然烘干的水滴数为 。
  则有 ，所以 。因为 取整数，要上取整。

C++代码

class Solution {
    inline int maxVal(vector<int>& a){
        int ans = a[0];
        for(int i=1; i<a.size(); ++i){
            if(a[i] > ans)
                ans = a[i];
        }
        return ans;
    }

    bool check(int m, int k, vector<int>& a){
        int cnt = 0;
        for(int i=0; i<a.size(); ++i){
            if(a[i] > m){
                cnt += (a[i]-m) / (k-1);
                if((a[i]-m)%(k-1))
                    ++cnt;
            }
            if(cnt > m)
                return false;
        }
        return true;
    }

public:
    /**
     * 计算最少要多少时间可以把所有的衣服全烘干
     * @param n int整型 n件衣服
     * @param a int整型vector n件衣服所含水量数组
     * @param k int整型 烘***1分钟可以烘干的水量
     * @return int整型
     */
    int solve(int n, vector<int>& a, int k) {
        // write code here
        int left = 1;
        int right = maxVal(a);
        if(k == 1)
            return right;
        while(left < right){
            int mid = left + ((right-left)>>1);
            if(check(mid, k, a))
                right = mid;
            else
                left = mid + 1;
        }
        return right;
    }
};