牛牛晾衣服 （二分）

題目連結：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;
    }
};