1723. 完成所有工作的最短时间

1723. 完成所有工作的最短时间

1. 状压+二分

这个写法跟这道题类似 1986. 完成任务的最少工作时间段

class Solution {
 public:
  int minimumTimeRequired(vector<int>& jobs, int k) {
    int n = jobs.size();
    vector<int> tot(1 << n);
    for (int i = 0; i < (1 << n); i++) {
      for (int j = 0; j < n; j++) {
        if (i & (1 << j)) {
          tot[i] = tot[i - (1 << j)] + jobs[j];
          break;
        }
      }
    }

    int l = 0, r = 0;
    for (auto i : jobs) {
      r += i;
      l = max(l, i);
    }

    while (l < r) {
      int x = (l + r) >> 1;
      // dp[i] : 处理集合为 i 的工作，需要最少员工的数量
      int dp[1 << n];
      memset(dp, 0x3f, sizeof dp);
      dp[0] = 0;  // 处理集合为0需要0个员工
      for (int i = 0; i < (1 << n); i++) {
        for (int s = i; s; s = (s - 1) & i) {
          if (tot[s] <= x) {
            dp[i] = min(dp[i], dp[i - s] + 1);
          }
        }
      }
      if (dp[(1 << n) - 1] <= k)
        r = x;
      else
        l = x + 1;
    }
    return l;
  }
};

2. 状压dp

跟这个题类似 1655. 分配重复整数

class Solution {
 public:
  int minimumTimeRequired(vector<int>& jobs, int k) {
    int 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];
      }
    }

    int dp[k][1 << n];
    memset(dp, 0x3f, sizeof dp);
    for (int i = 0; i < (1 << n); i++) {
      dp[0][i] = sum[i];
    }

    for (int i = 1; i < k; i++) {
      for (int j = 0; j < (1 << n); j++) {
        // 枚举子集
        for (int x = j; x; x = (x - 1) & j) {
          dp[i][j] = min(dp[i][j], max(dp[i - 1][j - x], sum[x]));
        }
      }
    }
    return dp[k - 1][(1 << n) - 1];
  }
};