题目
快手秋招笔试原题 没做出来orz
https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/description
给你 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.lengthm == workers.length1 <= n, m <= 5 * 1040 <= pills <= m0 <= tasks[i], workers[j], strength <= 109
题解
思路是二分查找 + 贪心。
提示 1
如果我们已经知道「一定」可以完成 k 个任务，那么：
- 我们可以在 tasks 中选择 k 个值最小的任务；
- 我们可以在 workers 中选择 k 个值最大的工人；
提示 2
如果我们可以完成 k 个任务，并且满足提示 1，那么一定可以完成 k−1 个任务，并且可以选择 k−1 个值最小的任务以及 k−1 个值最大的工人，同样满足提示 1。
思路与算法
根据提示 2，我们就可以使用二分查找的方法找到 k 的上界 k′，使得我们可以完成 k′个任务，但不能完成 k′+1 个任务。我们找到的 k′即为答案。
在二分查找的每一步中，当我们得到 k 个值最小的任务以及 k 个值最大的工人后，我们应该如何判断这些任务是否都可以完成呢？
我们可以考虑值最大的那个任务，此时会出现两种情况：
- 如果有工人的值大于等于该任务的值，那么我们一定不需要使用药丸，并且一定让值最大的工人完成该任务；
证明的思路为：由于我们考虑的是值最大的那个任务，因此所有能完成该任务的工人都能完成剩余的所有任务。因此如果一个值并非最大的工人（无论是否使用药丸）完成该任务，而值最大的工人完成了另一个任务，那么我们将这两个工人完成的任务交换，仍然是可行的。
- 如果所有工人的值都小于该任务的值，那么我们必须使用药丸让一名工人完成任务，并且一定让值最小的工人完成该任务；
这里的值最小指的是在使用药丸能完成任务的前提下，值最小的工人。
证明的思路为：由于我们考虑的是值最大的那个任务，因此所有通过使用药丸能完成该任务的工人都能完成剩余的所有任务。如果一个值并非最小的工人使用药丸完成该任务，而值最小的工人（无论是否使用药丸）完成了另一个任务，那么我们将这两个工人完成的任务交换，仍然是可行的。
因此，我们可以从大到小枚举每一个任务，并使用有序集合维护所有的工人。当枚举到任务的值为 t 时：
- 如果有序集合中最大的元素大于等于 t，那么我们将最大的元素从有序集合中删除；
- 如果有序集合中最大的元素小于 t，那么我们在有序集合中找出最小的大于等于 t−strength 的元素并删除；
对于这种情况，如果我们没有药丸剩余，或者有序集合中不存在大于等于 t−strength 的元素，那么我们就无法完成所有任务；
这样一来，我们就解决了二分查找后判断可行性的问题。
class Solution
{
public:
// 校验是否能完成x项任务
bool check(const vector<int> &tasks, const vector<int> &workers, int pills, int strength, int x)
{
multiset<int> wks;
for (int i = 0; i < x; i++)
{
// 选择x个力量值最大的工人,wks里面的元素升序排列
wks.insert(workers[i]);
}
// 选择x个最简单的任务,从难到易
for (int i = tasks.size() - x; i < tasks.size(); i++)
{
// 返回元素值为elem的第一个可安插位置，也就是元素值 >= elem的第一个元素位置
auto it = wks.lower_bound(tasks[i]);
if (it != wks.end())
{
// 不需要药丸即可完成任务i
wks.erase(it);
}
else
{
// 不需要药丸不能完成任务i,可尝试使用药丸;
if (pills > 0)
{
it = wks.lower_bound(tasks[i] - strength);
pills--;
if (it != wks.end())
{
// 说明it位置的工人使用一片药丸能够完成任务i
wks.erase(it);
}
else
{
// 使用药丸也不能完成任务i
return false;
}
}
// 没有药丸了
else
{
return false;
}
}
}
return true;
}
int maxTaskAssign(vector<int> &tasks, vector<int> &workers, int pills, int strength)
{
// 选择x个最简单的任务,从难到易 降序排列
sort(tasks.begin(), tasks.end(), greater<int>());
// 选择x个力量值最大的工人 降序排列
sort(workers.begin(), workers.end(), greater<int>());
int left = 0, right = min(tasks.size(), workers.size()), x;
// 使用二分查找的方法
while (left < right)
{
// 因为需要跳出while循环,left最多取right-1,在算x的时候可以将left+1,这样可以将right边界覆盖住
x = left + (right - left + 1) / 2; //防止int型溢出
if (check(tasks, workers, pills, strength, x))
{
// 左边界暂存满足条件的最大x
left = x;
}
else
{
// x项任务不能完成,收缩右边界
right = x - 1;
}
}
return left;
}
};