个人做的网站不能做淘客/谷歌推广和seo

1 题目描述

题目链接：https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/

给你一个整数数组 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 。

2 代码/C++

class Solution {
public:bool backtrack(vector<int>& jobs, vector<int>& workloads, int idx, int limit) {// 回溯迭代终止条件，分配完所有任务if (idx >= jobs.size()) {return true;}// 当前工作量int cur = jobs[idx];for (auto& workload : workloads) {// 将当前工作分配给工人，采用回溯法，依次给每个人分配if (workload + cur <= limit) {workload += cur; // 分配if (backtrack(jobs, workloads, idx + 1, limit)) {return true;}workload -= cur; // 不分配，回溯}// 两种情况下我们无需尝试继续分配工作，认为该limit下无可行解：// 1. 如果当前工人工作量为0，而当前工作又不能分配给他，说明分配方案已无法进行（经过工作量排序，这种情况不会出现）// 2. 或者当前工作恰能使该工人的工作量达到了上限，达到上限之后无法再给该工人分配工作，而剩下工作也无法继续分配            if (workload == 0 || workload + cur == limit) {break;}}return false;}bool check(vector<int>& jobs, int k, int limit) {// 定义一个wordloads来存放每个人的工作量，初始值均为0vector<int> workloads(k, 0);// 以backtrack函数判断limit是否合适return backtrack(jobs, workloads, 0, limit);}int minimumTimeRequired(vector<int>& jobs, int k) {// 将vector从大到小排序sort(jobs.begin(), jobs.end(), greater<int>()); // 定义二分查找上下限，下限是最大job，上限是所有job之和int l = jobs[0], r = accumulate(jobs.begin(), jobs.end(), 0); // 执行二分查找while (l < r) {// 计算上下限平均数int mid = (l + r) >> 1;// 调用check函数，确定mid是否能得到可行解，如果可以，则上限收缩if (check(jobs, k, mid)) {r = mid;// 如果mid不能得到可行解，则下限收缩} else {l = mid + 1;}}// 二分查找终止条件是上下限重合，也是完成所有工作的最小时间return l;}
};

3 代码解释

上面用到了一个sort函数进行排序

 sort(jobs.begin(), jobs.end(), greater<int>()); //从大到小排序sort(jobs.begin(), jobs.end(), less<int>()); //从小到大排序

如果不想用库函数，可以自己写一个快排函数，quickSort()，相应的代码如下：

class Solution {
public:bool backtrack(vector<int>& jobs, vector<int>& workloads, int idx, int limit) {// 回溯迭代终止条件，分配完所有任务if (idx >= jobs.size()) {return true;}// 当前工作量int cur = jobs[idx];for (auto& workload : workloads) {// 将当前工作分配给工人，采用回溯法，依次给每个人分配if (workload + cur <= limit) {workload += cur; // 分配if (backtrack(jobs, workloads, idx + 1, limit)) {return true;}workload -= cur; // 不分配，回溯}// 两种情况下我们无需尝试继续分配工作，认为该limit下无可行解：// 1. 如果当前工人工作量为0，而当前工作又不能分配给他，说明分配方案已无法进行（经过工作量排序，这种情况不会出现）// 2. 或者当前工作恰能使该工人的工作量达到了上限，达到上限之后无法再给该工人分配工作，而剩下工作也无法继续分配            if (workload == 0 || workload + cur == limit) {break;}}return false;}bool check(vector<int>& jobs, int k, int limit) {// 定义一个wordloads来存放每个人的工作量，初始值均为0vector<int> workloads(k, 0);// 以backtrack函数判断limit是否合适return backtrack(jobs, workloads, 0, limit);}void quickSort(int left, int right, vector<int> &vec){if (left >=  right)return; // 递归结束条件int i = left, j = right, base = vec[left], temp; // 选择最左边的数为basewhile(i<j){while(vec[j]<=base && i<j)j--;while(vec[i]>=base && i<j)i++;if(i<j){ // 将左边比base小的数和右边比base大的数进行交换temp = vec[j];vec[j] = vec[i];vec[i] = temp;}                }vec[left] = vec[i]; // 将base和双指针停止点（i或j）的数交换vec[i] = base;quickSort(left, i-1, vec); // 递归排序i之前的数quickSort(i+1, right, vec);// 递归排序i之后的数}int minimumTimeRequired(vector<int>& jobs, int k) {// 将vector从大到小排序//sort(jobs.begin(), jobs.end(), greater<int>()); quickSort(0, jobs.size()-1, jobs);// 定义二分查找上下限，下限是最大job，上限是所有job之和int l = jobs[0], r = accumulate(jobs.begin(), jobs.end(), 0); // 执行二分查找while (l < r) {// 计算上下限平均数int mid = (l + r) >> 1;// 调用check函数，确定mid是否能得到可行解，如果可以，则上限收缩if (check(jobs, k, mid)) {r = mid;// 如果mid不能得到可行解，则下限收缩} else {l = mid + 1;}}// 二分查找终止条件是上下限重合，也是完成所有工作的最小时间return l;}
};