leetcode你可以安排最多的任务数目(做题收获)

发布时间:2024年01月24日

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

二分加贪心,两个基础算法。

收获1:贪心力求消耗最小,这道题中会出现这样一种情况6 6 4和8 5 5匹配,且只有一个药加5点力气,如果把药给6用,变成11,6,4,那么能完成的任务数是2,如果把药给4,用,变成9,6,6那么能完成的任务数为3,所以贪心的思路不应该是大的和大的匹配,不够大就用药,而是碰到不够大的时候从最小的往大的找,找到用药后满足条件的最小值,这时既可以留下大的,又可以完成任务,此时消耗最小。

收获2:如何获取multiset的最大下标呢,!!prev()函数,头文件是#include<iterator>,返回该迭代器的前一个迭代器prev(ws.end)。

收获3:用lower_bound找最小符合,反之用upper_bound-1找最大符合。

下面是ac代码

class Solution {
public:
    int ans=0;
    bool check(vector<int>& tasks, vector<int>& workers, int p, int& strength,int mid){
        int fcpt=0,m=workers.size(),n=tasks.size();
        multiset<int>ws;
        for(int i=m-mid;i<m;i++){
            ws.insert(workers[i]);
        }
        for(int i=mid-1;i>=0;i--){
            if(auto it=prev(ws.end());*it>=tasks[i]){
                ws.erase(it);
            }
            else{
                if(!p)return false;
                auto rep=ws.lower_bound(tasks[i]-strength);
                if(rep==ws.end())return false;
                --p;
                ws.erase(rep);
            }
        }
        return true;
    }
    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        int n=tasks.size(),m=workers.size();
        int l=0,r=std::min(m,n)+1;
        std::sort(tasks.begin(),tasks.end());
        std::sort(workers.begin(),workers.end());
        while(l+1<r){
            int cpt=(l+r)/2;
            if(check(tasks,workers,pills,strength,cpt))l=cpt;
            else r=cpt;
        }
        return l;
    }
};

文章来源:https://blog.csdn.net/Colinnian/article/details/135833079
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。