文章目录
1. 题目
2. 解题
1. 题目
给你 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 * 10^4 0 <= pills <= m 0 <= tasks[i], workers[j], strength <= 10^9
2. 解题
直接二分查找答案 k，选择最强的 k 个人，去完成最简单的 k 个任务（如果 k 个人能完成 k 个任务， k+1 个人则不一定能完成 k+1 个任务，具有单调性）
注意判断是否可行的时候，要先遍历难的任务（如，任务3,5，人1, 3，药2，力量3，如果顺序遍历任务，任务3被人3完成，人1吃药+3无法完成任务5，如果从难到简单遍历，任务5被人3吃药+3完成，任务3被人1吃药+3完成，从难开始遍历更优）
注意：multiset 自带的 lower_bound 比 lower_bound(iter1, iter2, val) 快
class Solution { public: int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) { sort(tasks.begin(), tasks.end()); sort(workers.rbegin(), workers.rend()); int n = min(tasks.size(), workers.size()); int ans = 0, mid, l = 0, r = n; while(l <= r) { mid = (l+r)>>1;// 完成 mid 个任务 if(ok(tasks, workers, mid, pills, strength)) { ans = mid; l = mid+1; } else r = mid-1; } return ans; } bool ok(vector<int>& tasks, vector<int>& workers, int finish, int pills, int strength) { multiset<int> w(workers.begin(), workers.begin()+finish); // 最强的finish 个 工人 for(int i = finish-1; i >= 0; --i) // 先找难的任务 { int t = tasks[i]; auto it = w.lower_bound(t); if(it != w.end()) w.erase(it);//能直接完成 else if(pills > 0) { auto it1 = w.lower_bound(t-strength); if(it1 != w.end()) { w.erase(it1);//吃药能完成 pills--; } else return false; } else return false; } return true; } };
1308 ms 275.2 MB C++
