动易网站做值班表,设计一个自己公司网站开发,面试网站建设工程师,wordpress page id文章目录 前言思路主要思路关于f函数的剖析Code就到这#xff0c;铁子们下期见#xff01;#xff01;#xff01;#xff01; 前言
铁子们好啊#xff01;今天阿辉又给大家来更新新一道好题#xff0c;下面链接是23年9月27的华为笔试原题#xff0c;LeetCode上面的ha… 文章目录 前言思路主要思路关于f函数的剖析Code就到这铁子们下期见 前言
铁子们好啊今天阿辉又给大家来更新新一道好题下面链接是23年9月27的华为笔试原题LeetCode上面的hard难题阿辉带大伙来拿下它 你可以安排的最多任务数目
思路 二分和单调队列以及一丢丢贪心 主要思路 先按照任务难度和工人能力排序 二分的范围是[l,r)左闭右开l 0,r n1最多完成n个任务n取任务数与工人数的较小值因为左闭右开所以r取n1最少完成0个任务所以l取0 然后就是如何判断l与r的中点m是否是能够完成的任务数 排序的重要就在这里体现了我们取任务难度最小的m个与能力最强的m个工人如果能够完成那就能完成如果不能就完成不了
主逻辑代码
// 主函数用于找出可以分配的最大任务数量。int maxTaskAssign(vectorint tasks, vectorint workers, int pills, int strength) {int n min(tasks.size(), workers.size()); // 取任务数和工人数中较小的一个因为任务数不能超过工人数。int l 0; // 二分查找的左边界int r n1; // 二分查找的右边界sort(tasks.begin(), tasks.end()); // 将任务按难度排序sort(workers.begin(), workers.end()); // 将工人按能力排序// 二分查找确定最大可分配任务数while (l r) {int m l (r - l) / 2; // 中间点//f函数用于判断是否可以完成m个任务if (f(tasks, workers, pills, strength, m)) {l m 1; // 如果能完成m个任务则尝试增加任务数} else {r m; // 如果不能完成m个任务则减少任务数}}return l - 1; // 返回最终的任务数因为在二分查找结束时l指向的是第一个不能完成的任务数}关于f函数的剖析
f函数的空间复杂度是 O ( M ) O(M) O(M)因为i和j都只前进不回退也就是只遍历2次m长度的数组 N为任务数组与工人数组的较大值 然后主函数排序两个数组是 O ( N l o g N ) O(NlogN) O(NlogN)二分加上f函数最多也不超过 O ( N l o g N ) O(NlogN) O(NlogN) 所以时间复杂度 O ( N l o g N ) O(NlogN) O(NlogN) 空间复杂度低于 O ( N ) O(N) O(N)队列长度取决于完成任务的数量 int deque[50001]; // 一个双端队列用于存储可能通过使用或不使用药丸完成的任务。// 辅助函数用于判断是否能在当前条件下完成m个任务。bool f(vectorint ts, vectorint ws, int p, int s, int m) {int h 0, t 0; // 双端队列的头部和尾部指针//i指向最容易完成的第一个任务j指向能力第m强的工人//遍历m个最容易完成的任务以及能力最强的m个工人for (int i 0, j ws.size() - m; j ws.size(); j) {// 遍历每一个工人并尝试分配任务while (i m ts[i] ws[j]) {// 如果当前任务可以由工人直接完成则将其加入队列deque[t] ts[i];}//经过上面的if如果队列里面没东西说明该试试药了//如果队列里面有东西可能是前一个工人嗑药留下的if (h t || ws[j] deque[h]) {// 如果队列为空或当前工人无法完成队列头部的任务则尝试使用药丸--p; // 使用一颗药丸while (i m ts[i] ws[j] s) {// 将可以通过使用药丸完成的任务加入队列deque[t] ts[i];}if (h t || p 0 || ws[j] s deque[h]) {// 如果队列依然为空或药丸用完或即使使用药丸也无法完成队列头部的任务则返回falsereturn false;}--t; // 上面没返回说明嗑药有用完成最难的任务一点子贪心各位肯定能懂队列尾部指针前移} else {//否则h; // 工人直接完成了队列头部的任务队列头部指针后移}}//能走到这就说明能完成return true; Code
class Solution {
public:// 主函数用于找出可以分配的最大任务数量。int maxTaskAssign(vectorint tasks, vectorint workers, int pills, int strength) {int n min(tasks.size(), workers.size()); // 取任务数和工人数中较小的一个因为任务数不能超过工人数。int l 0; // 二分查找的左边界int r n1; // 二分查找的右边界sort(tasks.begin(), tasks.end()); // 将任务按难度排序sort(workers.begin(), workers.end()); // 将工人按能力排序// 二分查找确定最大可分配任务数while (l r) {int m l (r - l) / 2; // 中间点if (f(tasks, workers, pills, strength, m)) {l m 1; // 如果能完成m个任务则尝试增加任务数} else {r m; // 如果不能完成m个任务则减少任务数}}return l - 1; // 返回最终的任务数因为在二分查找结束时l指向的是第一个不能完成的任务数}int deque[50001]; // 一个双端队列用于存储可能通过使用或不使用药丸完成的任务。// 辅助函数用于判断是否能在当前条件下完成m个任务。bool f(vectorint ts, vectorint ws, int p, int s, int m) {int h 0, t 0; // 双端队列的头部和尾部指针for (int i 0, j ws.size() - m; j ws.size(); j) {// 遍历每一个工人并尝试分配任务while (i m ts[i] ws[j]) {// 如果当前任务可以由工人直接完成则将其加入队列deque[t] ts[i];}if (h t || ws[j] deque[h]) {// 如果队列为空或当前工人无法完成队列头部的任务则尝试使用药丸--p; // 使用一颗药丸while (i m ts[i] ws[j] s) {// 将可以通过使用药丸完成的任务加入队列deque[t] ts[i];}if (h t || p 0 || ws[j] s deque[h]) {// 如果队列依然为空或药丸用完或即使使用药丸也无法完成队列头部的任务则返回falsereturn false;}--t; // 完成一个任务队列尾部指针前移} else {h; // 工人直接完成了队列头部的任务队列头部指针后移}}return true; // 如果所有工人都成功分配了任务则返回true}
};就到这铁子们下期见
