除掉相同的工人和药丸

发布时间：2025-06-24 18:44:57 作者：北方职教升学中心阅读量：472

|
|如果程序是一条龙，那算法就是他的是睛|

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境：

VS2022 C++17

方案一：b和一片药丸。双向队列que记录所有吃药丸后能完成当前任务的工人，升序排列。
给你下标从 0 开始的整数数组tasks 和 workers 以及两个整数 pills 和 strength ，请你返回最多有多少个任务可以被完成。
如果方案二，能完成任务，则方案一也能完成任务。

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 号工人药丸。每个工人的力量值保存在下标从 0 开始的整数数组 workers 中，第 j 个工人的力量值为 workers[j] 。

代码

核心代码

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;
}
};

优化

如果有工人，能直接完成。
除掉相同的工人和药丸。
示例 1：
输入：tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1
输出：3
解释：
我们可以按照如下方案安排药丸：

给 0 号工人药丸。每个工人只能完成一个任务，且力量值需要大于等于该任务的力量要求值（即 workers[j] >= tasks[i] ）。否则，吃药丸完成。
除此以外，你还有 pills 个神奇药丸，可以给一个工人的力量值增加 strength 。
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 号工人药丸。
1 号工人完成任务 0（6 >= 5）
2 号工人完成任务 2（4 + 5 >= 8）
4 号工人完成任务 3（6 >= 5）
参数范围：
n == tasks.length
m == workers.length
1 <= n, m <= 5 * 10⁴
0 <= pills <= m
0 <= tasks[i], workers[j], strength <= 10⁹

分析

时间复杂度

O(lognnlogn)。

为什么能不吃药丸，就不吃药丸

假定任务i，b吃药丸才能完成，c可直接完成。
方案一：c直接完成。因为药丸可以给b以外的工人吃。因为任务是越来越容易，能完成当前任务，则能完成之后的任意任务。

本文涉及知识点

C++贪心
二分查找算法合集

题目

给你 n 个任务和 m 个工人。
方案二：c。

代码

classSolution{public:intmaxTaskAssign(vector<int>&tasks,vector<int>&workers,constintpills,constintstrength){autoCan =[&](constintdoNum){intiNeedPill =0;std::vector<int>vWork(workers.begin()+workers.size()-doNum ,workers.end());//派出的工人std::deque<int>que;for(inti =doNum -1,j =i;i >=0;i--){while((j>=0)&&(vWork[j]+strength >=tasks[i])){que.emplace_front(vWork[j--]);}if(que.empty()){returnfalse;//没有共人能完成任务}if(que.back()>=tasks[i]){que.pop_back();continue;}if(iNeedPill >=pills){//没药丸了returnfalse;}que.pop_front();iNeedPill++;}returntrue;};sort(tasks.begin(),tasks.end());sort(workers.begin(),workers.end());intn =min(tasks.size(),workers.size());intleft =0,right =n +1;//左闭右开while(right -left >1){constautomid =left +(right -left)/2;if(Can(mid)){left =mid;}else{right =mid;}}returnleft;}};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

二分查找

0个任务一定可以完成，随着任务数增加，变得不可完成。b吃药后，能完成余下任意任务。
注意：反之不成立。也就是我们常说的专业的人做专业的事。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 0 开始的整数数组 tasks 中，第 i 个任务需要 tasks[i] 的力量才能完成。

完成doNum个任务

最强的doNum个工人是否能完成最简单的doNum个任务。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、任务是从难到容易的。你可以决定给哪些工人使用药丸，但每个工人最多只能使用一片药丸。

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

给 0 号和 1 号工人药丸。
方案二：b吃药丸完成。从困难到容易枚举任务，如果有工人能完成，则直接完成。子墨子言之：事无终始，无务多业

。则选择任意一个能完成的工人，不必选择最弱的工人。C++入职培训等课程
https://edu.csdn.net/lecturer/6176

预约在线报名

学生姓名：
男女
联系电话：
意向班型：
我是学生我是家长