文章目录

• 前言
• 思路
• 主要思路
• 关于f函数的剖析
• Code
• • 就到这，铁子们下期见！！！！

    前言

    铁子们好啊！今天阿辉又给大家来更新新一道好题，下面链接是23年9月27的华为笔试原题，LeetCode上面的hard难题，阿辉带大伙来拿下它！！！

    你可以安排的最多任务数目

    思路

    二分和单调队列以及一丢丢贪心

    主要思路

    • 先按照任务难度和工人能力排序

    • 二分的范围是[l,r)左闭右开，l = 0,r = n+1，最多完成n个任务，n取任务数与工人数的较小值，因为左闭右开，所以r取n+1，最少完成0个任务，所以l取0

    • 然后就是如何判断l与r的中点m是否是能够完成的任务数

      • 排序的重要就在这里体现了，我们取任务难度最小的m个与能力最强的m个工人如果能够完成，那就能完成，如果不能就完成不了

        主逻辑代码：

        // 主函数，用于找出可以分配的最大任务数量。
            int maxTaskAssign(vector& tasks, vector& workers, int pills, int strength) {
                int n = min(tasks.size(), workers.size()); // 取任务数和工人数中较小的一个，因为任务数不能超过工人数。
                int l = 0; // 二分查找的左边界
                int r = n+1; // 二分查找的右边界
                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(vector& ts, vector& 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]) {
                            // 如果队列依然为空，或药丸用完，或即使使用药丸也无法完成队列头部的任务，则返回false
                            return false;
                        }
                        --t; // 上面没返回说明嗑药有用，完成最难的任务，一点子贪心各位肯定能懂，队列尾部指针前移
                    } else {//否则
                        ++h; // 工人直接完成了队列头部的任务，队列头部指针后移
                    }
                }
                //能走到这就说明能完成
                return true; 
        

        Code

        class Solution {
        public:
           
            // 主函数，用于找出可以分配的最大任务数量。
            int maxTaskAssign(vector& tasks, vector& workers, int pills, int strength) {
                int n = min(tasks.size(), workers.size()); // 取任务数和工人数中较小的一个，因为任务数不能超过工人数。
                int l = 0; // 二分查找的左边界
                int r = n+1; // 二分查找的右边界
                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(vector& ts, vector& 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]) {
                            // 如果队列依然为空，或药丸用完，或即使使用药丸也无法完成队列头部的任务，则返回false
                            return false;
                        }
                        --t; // 完成一个任务，队列尾部指针前移
                    } else {
                        ++h; // 工人直接完成了队列头部的任务，队列头部指针后移
                    }
                }
                return true; // 如果所有工人都成功分配了任务，则返回true
            }
        };
        

        就到这，铁子们下期见！！！！

        

         
         汕头网站建设工作  网站开发公司如何运营  湖北当阳网当阳新闻  seo积分系统  公司网站建设和维护  宿迁人才网最新招聘信息网