第三场（C-牛牛晾衣服）

链接：https://ac.nowcoder.com/acm/contest/6220/C
来源：牛客网

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

示例1
输入
3,[2,3,9],5
输出
3
说明
前两分钟对第三件衣服进行烘***烘干，使得衣服的水份分别为0，1，0，所以最快三分钟可以烘干。
备注:
第一个参数n()，代表一共有多少件衣服。
第二个参数为n个数()组成的数组，代表n件衣服分别有多少水滴水。
第三个参数k()，代表烘***每分钟能烘干k滴水。
程序应返回：一个整数，代表使n件衣服全部干燥所需要的最少的时间。
解题思路
显然，需要的最长时间是中的最大值。答案区间确定，可以采用二分答案的方法。
注意特殊情况k==1，这种情况下将烘***也当成自然烘干就好，直接返回最大值。
根据候选答案mid，判断mid是否满足条件（注意烘***的实际效果是每分钟烤干k-1滴水）。
代码

class Solution {
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 l = 0, r = 0;
        for(int it : a) r = max(r, it);
        if(k == 1) return r;
        while(l < r) {
            int mid = l + (r - l) / 2, t = 0;
            for(int it : a) {
                if(it <= mid) continue;
                t += (it - mid + k - 2) / (k - 1);
                if(t > mid) break;
            }
            if(t > mid) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};