作者推荐
[二分查找]LeetCode2040:两个有序数组的第 K 小乘积
本文涉及的基础知识点
二分查找算法合集
题目
给你 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 * 104 0 <= pills <= m 0 <= tasks[i], workers[j], strength <= 109
分析
时间复杂度
O(lognnlogn)。二分查找可以完成的任务数，时间复杂度O(logn)；枚举任务，时间复杂度O(n)；每个任务二分查找，时间复杂度O(logn)。
二分查找
0个任务一定可以完成，随着任务数增加，变得不可完成。寻找最后一个可以完成任务的doNum，左闭右开空间。
完成doNum个任务
最强的doNum个工人是否能完成最简单的doNum个任务。从困难到容易枚举任务，如果有工人能完成，则直接完成。否则，吃药丸完成。无论是否吃药丸，在能完成任务的情况下，派最弱的人。
为什么能不吃药丸，就不吃药丸
假定任务i，b吃药丸才能完成，c可直接完成。 方案一：c直接完成。 方案二：b吃药丸完成。 除掉相同的工人和药丸。 方案一：b和一片药丸。 方案二：c。 如果方案二，能完成任务，则方案一也能完成任务。b吃药后，能完成余下任意任务。任务是从难到容易的。 注意：反之不成立。因为药丸可以给b以外的工人吃。
代码
核心代码
class Solution { public: int maxTaskAssign(vector& tasks, vector& workers, const int pills, const int strength) { auto Can = [&](const int doNum) { int iNeedPill = 0; std::multiset setWork(workers.rbegin() , workers.rbegin()+doNum); for (int i = doNum - 1; i >= 0; i–) { auto it = setWork.lower_bound(tasks[i]); if (setWork.end() != it) { setWork.erase(it); continue; } if (iNeedPill >= pills) {//没药丸了 return false; } it = setWork.lower_bound(tasks[i] - strength); if (setWork.end() == it) { return false;//吃了药丸也无法完成任务 } setWork.erase(it); iNeedPill++; } return true; }; sort(tasks.begin(), tasks.end()); sort(workers.begin(), workers.end()); int n = min(tasks.size(), workers.size()); int left = 0, right = n + 1;//左闭右开 while (right - left > 1) { const auto mid = left + (right - left) / 2; if (Can(mid)) { left = mid; } else { right = mid; } } return left; } };
测试用例
template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } }
template void Assert(const T& t1, const T& t2) { assert(t1 == t2); }
int main() { vector tasks, workers; int pills, strength, res; { Solution slu; tasks = { 3, 2, 1 }, workers = { 0, 3, 3 }, pills = 1, strength = 1; auto res = slu.maxTaskAssign(tasks, workers, pills, strength); Assert(3, res); } { Solution slu; tasks = { 5, 4 }, workers = { 0, 0, 0 }, pills = 1, strength = 5; auto res = slu.maxTaskAssign(tasks, workers, pills, strength); Assert(1, res); } { Solution slu; tasks = { 10, 15, 30 }, workers = { 0, 10, 10, 10, 10 }, pills = 3, strength = 10; auto res = slu.maxTaskAssign(tasks, workers, pills, strength); Assert(2, res); } { Solution slu; tasks = { 5, 9, 8, 5, 9 }, workers = { 1, 6, 4, 2, 6 }, pills = 1, strength = 5; auto res = slu.maxTaskAssign(tasks, workers, pills, strength); Assert(3, res); }
//CConsole::Out(res);
}
2023年3月版
class Solution { public: int maxTaskAssign(vector& tasks, vector& workers, int pills, int strength) { const int iNum = min(tasks.size(), workers.size()); std::sort(tasks.begin(), tasks.end()); std::sort(workers.begin(), workers.end()); return Rev(0, iNum + 1, tasks, workers, pills, strength); } int Rev(int iMin, int iMax, const vector& tasks, const vector& workers, int pills, int strength) { if (iMin + 1 == iMax) { return iMin; } const int iMid = (iMin + iMax) / 2; if (Can(iMid, tasks, workers, pills, strength)) { return Rev(iMid, iMax, tasks, workers, pills, strength); } return Rev(0, iMid, tasks, workers, pills, strength); } bool Can(int iFinishNum, const vector& tasks, const vector& workers, int pills, int strength) { std::multiset setWorks(workers.begin() + workers.size() - iFinishNum, workers.end()); for (int i = iFinishNum - 1; i >= 0;i–) { if (tasks[i] <= *setWorks.rbegin()) { setWorks.erase(std::prev(setWorks.end())); continue; } if (pills <= 0) { return false; } auto it = setWorks.lower_bound(tasks[i] - strength); if (setWorks.end() == it ) { return false; } pills–; setWorks.erase(it); } return true; } };
优化
如果有工人，能直接完成。则选择任意一个能完成的工人，不必选择最弱的工人。因为任务是越来越容易，能完成当前任务，则能完成之后的任意任务。双向队列que记录所有吃药丸后能完成当前任务的工人，升序排列。先判断队尾能否直接完成，否则判断队首能否吃药丸完成。
代码
class Solution {
public:
int maxTaskAssign(vector
auto Can = [&](const int doNum)
{
int iNeedPill = 0;
std::vector
std::deque
for (int i = doNum - 1, j = i; i >= 0; i--)
{
while ((j>=0)&&(vWork[j]+strength >= tasks[i]))
{
que.emplace_front(vWork[j--]);
}
if (que.empty())
{
return false;//没有共人能完成任务
}
if (que.back() >= tasks[i])
{
que.pop_back();
continue;
}
if (iNeedPill >= pills)
{//没药丸了
return false;
}
que.pop_front();
iNeedPill++;
}
return true;
};
sort(tasks.begin(), tasks.end());
sort(workers.begin(), workers.end());
int n = min(tasks.size(), workers.size());
int left = 0, right = n + 1;//左闭右开
while (right - left > 1)
{
const auto mid = left + (right - left) / 2;
if (Can(mid))
{
left = mid;
}
else
{
right = mid;
}
}
return left;
}
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。子墨子言之：事无终始，无务多业
。也就是我们常说的专业的人做专业的事。 | |如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17 或者 操作系统：win10 开发环境：
VS2022 C++17
好文链接
您阅读本篇文章共花了：
发表评论