class Solution {
public:
int minimumTimeRequired(vector<int>& jobs, int k) {
}
};
1723. 完成所有工作的最短时间
给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。
请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。
返回分配方案中尽可能 最小 的 最大工作时间 。
示例 1：
输入：jobs = [3,2,3], k = 3 输出：3 解释：给每位工人分配一项工作，最大工作时间是 3 。
示例 2：
输入：jobs = [1,2,4,7,8], k = 2 输出：11 解释：按下述方式分配工作： 1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11） 2 号工人：4、7（工作时间 = 4 + 7 = 11） 最大工作时间是 11 。
提示：
1 <= k <= jobs.length <= 121 <= jobs[i] <= 107原站题解
golang 解法, 执行用时: 100 ms, 内存消耗: 6.2 MB, 提交时间: 2022-11-19 20:36:50
func minimumTimeRequired(jobs []int, k int) int {
n := len(jobs)
m := 1 << n
sum := make([]int, m)
for i := 1; i < m; i++ {
x := bits.TrailingZeros(uint(i))
y := i ^ 1<<x
sum[i] = sum[y] + jobs[x]
}
dp := make([][]int, k)
for i := range dp {
dp[i] = make([]int, m)
}
for i, s := range sum {
dp[0][i] = s
}
for i := 1; i < k; i++ {
for j := 0; j < (1 << n); j++ {
minn := math.MaxInt64
for x := j; x > 0; x = (x - 1) & j {
minn = min(minn, max(dp[i-1][j-x], sum[x]))
}
dp[i][j] = minn
}
}
return dp[k-1][(1<<n)-1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-11-19 20:36:29
func minimumTimeRequired(jobs []int, k int) int {
n := len(jobs)
sort.Sort(sort.Reverse(sort.IntSlice(jobs)))
l, r := jobs[0], 0
for _, v := range jobs {
r += v
}
return l + sort.Search(r-l, func(limit int) bool {
limit += l
workloads := make([]int, k)
var backtrack func(int) bool
backtrack = func(idx int) bool {
if idx == n {
return true
}
cur := jobs[idx]
for i := range workloads {
if workloads[i]+cur <= limit {
workloads[i] += cur
if backtrack(idx + 1) {
return true
}
workloads[i] -= cur
}
// 如果当前工人未被分配工作，那么下一个工人也必然未被分配工作
// 或者当前工作恰能使该工人的工作量达到了上限
// 这两种情况下我们无需尝试继续分配工作
if workloads[i] == 0 || workloads[i]+cur == limit {
break
}
}
return false
}
return backtrack(0)
})
}
golang 解法, 执行用时: 160 ms, 内存消耗: 3.5 MB, 提交时间: 2022-11-19 20:35:23
func minimumTimeRequired(a []int, k int) int {
n := 1 << len(a)
sum := make([]int, n)
for i, v := range a {
for j, bit := 0, 1<<i; j < bit; j++ {
sum[bit|j] = sum[j] + v
}
}
f := append([]int{}, sum...)
for i := 1; i < k; i++ {
for j := n - 1; j > 0; j-- {
for s := j; s > 0; s = (s - 1) & j {
f[j] = min(f[j], max(f[j^s], sum[s]))
}
}
}
return f[n-1]
}
func min(a, b int) int { if a > b { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }