牛牛晾衣服 （二分）

题目链接：https://ac.nowcoder.com/acm/contest/6220/C

题意

• 有n件衣服刚洗好，每件衣服都有ai滴水，现在有两种方式晾干
• 第一种是烘干机每分钟烘干k滴水，但是一次只能烘干一件衣服
• 第二种是自然烘干，当烘干机工作时，其他衣服自然烘干

思路 

• 二分。
• 二分烘干机使用次数。当烘干机工作时，其他衣服自然烘干，所以烘干机的效率是k-1。

AC代码

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=1,r=0,ans=0;
        for(auto i:a){
            r=max(r,i);//二分右值是最湿的衣服
        }
        while(l<=r){
            int mid=l+r>>1,cnt=mid;
            for(auto i:a){
                if(i>mid)cnt-=(i-mid+k-2)/(k-1);//向上取整，烘完为止，i<=mid的衣服在烘干机工作的时候自然烘干了
                if(cnt<0)break;
            }
            if(cnt>=0)r=mid-1,ans=mid;//cnt>=0说明使用mid次烘干机足以烘干所有
            else l=mid+1;
        }
        return ans;
    }
};