问题描述
给你 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 * 10⁴0 <= pills <= m0 <= tasks[i], workers[j], strength <= 10⁹
解题思路
二分答案+贪心。
我们假设答案为ans，那么一定是前ans个消耗精力最小的任务被后ans个力量最大的工人完成了。
将工人按力量值从小到大排序，将task用map来存储，二分答案进行判断时，遍历工人，先与map.begin()->first比较，如果大于等于，更新map，否则需要吃药，吃药之后必须选择小于等于当前力量的消耗精力最大的任务来处理，如果还是小于map.bein()->first，则return false，说明mid > ans。
建议使用左闭右闭。
代码
class Solution {
public:
bool check(int num, vector<int> &tasks, vector<int> &workers, int pills, map<int, int> mp, int strength) {
for (int i = 0, j = workers.size() - num; i < tasks.size() && j < workers.size(); ++i, ++j) {
if (mp.begin()->first > workers[j]) {
if (pills <= 0) {
return false;
} else {
if (mp.begin()->first > strength + workers[j]) {
return false;
} else {
auto iter = mp.lower_bound(strength + workers[j]);
if (iter->first == strength + workers[j]) {
--iter->second;
if (iter->second == 0) {
mp.erase(iter);
}
} else {
--iter;
--iter->second;
if (iter->second == 0) {
mp.erase(iter);
}
}
--pills;
}
}
} else {
mp.begin()->second--;
if (mp.begin()->second == 0) {
mp.erase(mp.begin());
}
}
}
return true;
}
int maxTaskAssign(vector<int> &tasks, vector<int> &workers, int pills, int strength) {
// 对工人的力量值从小到大排序
// 对任务的所需力量值从小到大排序
// 二分+贪心
int m = std::min(workers.size(), tasks.size());
std::sort(tasks.begin(), tasks.end());
std::sort(workers.begin(), workers.end());
map<int, int> mp;
for (int i = 0; i < tasks.size(); i++) {
mp[tasks[i]]++;
}
int left = 0, right = m;
while (left < right) {
int mid = left + (right - left) / 2;
if (check(mid, tasks, workers, pills, mp, strength)) {
left = mid + 1;
} else {
right = mid;
}
}
if (check(left, tasks, workers, pills, mp, strength))
return left;
return left - 1;
}
};