第65场双周赛D（二分+贪心）

Trace

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

传送门：https://leetcode-cn.com/problems/maximum-number-of-tasks-you-can-assign/

给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 0 开始的整数数组 tasks 中，第 i 个任务需要 tasks[i] 的力量才能完成。每个工人的力量值保存在下标从 0 开始的整数数组 workers 中，第 j 个工人的力量值为 workers[j] 。每个工人只能完成一个任务，且力量值需要 大于等于 该任务的力量要求值（即 workers[j] >= tasks[i] ）。

除此以外，你还有 pills 个神奇药丸，可以给 一个工人的力量值 增加 strength 。你可以决定给哪些工人使用药丸，但每个工人最多只能使用一片药丸。

给你下标从 0 开始的整数数组tasks 和 workers 以及两个整数 pills 和 strength ，请你返回最多有多少个任务可以被完成。

示例 1：

输入：tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 2（0 + 1 >= 1）
- 1 号工人完成任务 1（3 >= 2）
- 2 号工人完成任务 0（3 >= 3）

示例 2：

输入：tasks = [5,4], workers = [0,0,0], pills = 1, strength = 5
输出：1
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 0（0 + 5 >= 5）

示例 3：

输入：tasks = [10,15,30], workers = [0,10,10,10,10], pills = 3, strength = 10
输出：2
解释：
我们可以按照如下方案安排药丸：
- 给 0 号和 1 号工人药丸。
- 0 号工人完成任务 0（0 + 10 >= 10）
- 1 号工人完成任务 1（10 + 10 >= 15）

示例 4：

输入：tasks = [5,9,8,5,9], workers = [1,6,4,2,6], pills = 1, strength = 5
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 2 号工人药丸。
- 1 号工人完成任务 0（6 >= 5）
- 2 号工人完成任务 2（4 + 5 >= 8）
- 4 号工人完成任务 3（6 >= 5）

提示：

n == tasks.length
m == workers.length
1 <= n, m <= 5 * 1e4
0 <= pills <= m
0 <= tasks[i], workers[j], strength <= 1e9

思路

二分+贪心

假如使用药丸以后，$k$个任务可以被完成，那么小于$k$个任务也一定能完成，求满足条件的最大的$k$，考虑二分。

需要检查$mid$个任务是否可以被完成，如何检查？

假设可以完成$k$个任务，那么给$workers$中力量最大的k个人使用药丸以后，去完成$tasks$中需要力量最小的$k$个任务，一定可以完成。

从易到难遍历最简单的$k$个任务，然后从最强的$k$个$workers$中由弱到强匹配，看能否完成（由弱到强匹配为什么最优？因为假如当前最弱$worker$可以满足，那么任意其它$worker$也可以满足，交换后仍然可行）；如果不能完成，则给当前工人使用药丸，然后匹配能满足的最难的任务A（为什么最优，因为如果匹配最简单的任务B，另一个$worker$也可以满足A，交换后仍然可行）如果存在不能匹配则失败。

程序

class Solution {
public:
    // 9.52-10.45
    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        // 二分
        sort(tasks.begin(),tasks.end(),less<int>());
        sort(workers.begin(),workers.end(),less<int>());
        int m=workers.size();
        int n=tasks.size();
        int l=0,r=min(m,n);
        auto check=[&](int k)->bool{
            // 从小到大匹配tasks
            // tasks: tasks[0]...tasks[k-1]
            // workers[m-k]...workers[m-1]
            multiset<int> t(tasks.begin(),tasks.begin()+k);
            int use=0;
            for(int i=m-k;i<m;i++){
                if(*t.begin()<=workers[i]){
                    t.erase(t.begin());
                    continue;
                }
                // 给workers[i]使用药丸，然后找workers[i]+strength大于等于的最大的tasks
                use+=1;
                if(use>pills) return false;
                int now_strength=workers[i]+strength;
                // lower_bound 返回数组中第一个大于等于num的位置
                // upper_bound 返回数组中第一个大于num的位置
                // auto it=upper_bound(t.begin(),t.end(),now_strength);
                auto it=t.upper_bound(now_strength);
                if(it==t.begin()){
                    return false;
                }
                it--;
                t.erase(it);
            }
            return true;
        };

        while(l<r){
            // cout<<l<<" "<<r<<endl;
            int mid=(l+r+1)>>1;
            if(check(mid)){
                l=mid;
            }
            else{
                r=mid-1;
            }
        }
        return l;

    }
};