怎样为公司做网站,网站开发 后端返回前端一个地址 有什么用,做公众号一个月挣多少钱,印象笔记 wordpress文章目录1. 题目2. 解题1. 题目
给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成#xff0c;需要的力量值保存在下标从 0 开始的整数数组 tasks 中#xff0c;第 i 个任务需要 tasks[i] 的力量才能完成。 每个工人的力量值保存在下标从 0 开始的整数数组 worke…
文章目录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 号工人完成任务 20 1 1
- 1 号工人完成任务 13 2
- 2 号工人完成任务 03 3示例 2
输入tasks [5,4], workers [0,0,0], pills 1, strength 5
输出1
解释
我们可以按照如下方案安排药丸
- 给 0 号工人药丸。
- 0 号工人完成任务 00 5 5示例 3
输入tasks [10,15,30], workers [0,10,10,10,10], pills 3, strength 10
输出2
解释
我们可以按照如下方案安排药丸
- 给 0 号和 1 号工人药丸。
- 0 号工人完成任务 00 10 10
- 1 号工人完成任务 110 10 15示例 4
输入tasks [5,9,8,5,9], workers [1,6,4,2,6], pills 1, strength 5
输出3
解释
我们可以按照如下方案安排药丸
- 给 2 号工人药丸。
- 1 号工人完成任务 06 5
- 2 号工人完成任务 24 5 8
- 4 号工人完成任务 36 5提示
n tasks.length
m workers.length
1 n, m 5 * 10^4
0 pills m
0 tasks[i], workers[j], strength 10^9来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-number-of-tasks-you-can-assign 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
直接二分查找答案 k选择最强的 k 个人去完成最简单的 k 个任务如果 k 个人能完成 k 个任务 k1 个人则不一定能完成 k1 个任务具有单调性注意判断是否可行的时候要先遍历难的任务如任务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(vectorint tasks, vectorint 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 (lr)1;// 完成 mid 个任务if(ok(tasks, workers, mid, pills, strength)){ans mid;l mid1;}elser mid-1;}return ans;}bool ok(vectorint tasks, vectorint workers, int finish, int pills, int strength){multisetint 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--;}elsereturn false;}else return false;}return true;}
};1308 ms 275.2 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
