LC 1723. Find Minimum Time to Finish All Jobs (dp+二分)

link

class Solution {
public:
    int n;
    int minimumTimeRequired(vector<int>& jobs, int k) {
        n=jobs.size();
        vector<int> sum(1<<n);
        for(int i=1;i<(1<<n);i++){
            for(int j=0;j<n;j++){
                if(i&(1<<j)){
                    sum[i]=sum[i-(1<<j)]+jobs[j];
                    break;
                }
            }
        }
        int left=0;
        int right=0;
        for(int i:jobs){
            left=max(left,i);
            right+=i;
        }
        while(left<=right){
            int mid=left+(right-left)/2;
            int workers=helper(mid,sum);
            if(workers<=k) right=mid-1;
            else left=mid+1;
        }
        return left;
    }

    int helper(int limit, vector<int>& sum){
        vector<int> dp(1<<n,INT_MAX);
        dp[0]=0;
        for(int i=1;i<(1<<n);i++){
            for(int j=i;j>0;j= ((j-1)&i)){
                if(sum[j]<=limit) dp[i]=min(dp[i],1+dp[i-j]);
            }
        }
        return dp[(1<<n)-1];
    }
};

LC 1723. Find Minimum Time to Finish All Jobs (dp+二分)

原文：https://www.cnblogs.com/FEIIEF/p/14263704.html