牛客编程巅峰赛S1第3场 - 青铜&白银 C.牛牛晾衣服(二分)

题意:有\(n\)件衣服,每件衣服都有\(a_{i}\)滴水,所有衣服每分钟都能自然烘干\(1\)滴水,或者用烘干机,每分钟可以烘干\(k\)滴水,问最快多少分钟可以使所有衣服都烘干.
题解:这题和之前的那个拔苗助长感觉一样啊....都是二分答案.

先把\(a\)排个序,然后左区间\(l=1\),右区间\(r=a[n-1]\),因为答案肯定是单调的,大的满足,小的一定也满足,所以每次满足情况时更新右区间,具体的,每件衣服都能自然烘干\(mid\)滴水,然后枚举所有衣服,若不能自然烘干\((a_{i}-mid>0)\),那么就要用烘干机,如果使用烘干机的时间大于\(mid\),那么肯定不满足情况.

代码:

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

        sort(a.begin(),a.end());

        int l=1,r=a[n-1];

        while(l<r){          //向左二分

            int mid=(l+r)>>1;

            int tmp=mid;

            for(int i=0;i<n;++i){

                if(a[i]-mid>0){

                    tmp-=(a[i]-mid-1)/(k-1)+1;   //上取整

                }

                if(tmp<0) break;    //优化

            }

            if(tmp>=0){

                r=mid;    //更新右区间

            }

            else{

                l=mid+1;

            }

        }

        return r;

    }

};

巴特西

牛客编程巅峰赛S1第3场 - 青铜&白银 C.牛牛晾衣服(二分)

最新文章

热门文章