自己能建设网站,京东网上购物商城购物,无锡设计公司有哪些,metro风格网站开发题目链接#xff1a;https://leetcode.cn/problems/most-profit-assigning-work/
题目大意#xff1a;给出一串任务#xff0c;difficulty表示任务难度#xff0c;profit表示任务的收益#xff08;以下简称diff和pro#xff09;。给出一串工人的能力worker。每个工人只能…题目链接https://leetcode.cn/problems/most-profit-assigning-work/
题目大意给出一串任务difficulty表示任务难度profit表示任务的收益以下简称diff和pro。给出一串工人的能力worker。每个工人只能做一个任务且工人只能完成难度小于等于它能力的任务。同一人物可以完成多次。
思路题目的关键是给每个工人找到【难度小于等于其能力的】【收益最大的】任务。
一开始的思路暴力搜索果不其然寄了。。。
然后想到了前两天用过的线段树。先用一个mapint, int pf记录某个diff能得到的最大的pro。这是为了当出现【多个任务难度相同收益却不同】的情况时只记录收益最大的那个任务。因此map的存储量应该是最小的。
线段树tree[]存的是【当前节点的区间内最大收益】。在初始化时用updateTree()方法一一插入叶子节点并且给每个非叶子节点记录左右儿子最大的收益。
随后给每个工人查询区间[1, worker[i]]内最大的收益。
几个例子在IDE里都通过了但是leetcode里就是有heap-use-after-free的错误查了查意思是引用了已经free掉的空间。然而我并没有debug出是哪里用了非法的空间。因此暂且先放这里。
线段树方法完整代码
class Solution {
public:vectorint tree;void updateTree(int root, int l, int r, int i, int val) {if (l r) {tree[root] val;return;}int mid (lr) / 2;if (i mid) {updateTree(root*2, l, mid, i, val);}else {updateTree(root*21, mid1, r, i, val);}tree[root] max(tree[root*2], tree[root*21]);}int getMax(int root, int l, int r, int L, int R) {if (L l r R)return tree[root];int ret 0;int mid (lr)/2;if (L mid)ret getMax(root*2, l, mid, L, R);if (R mid)ret max(ret, getMax(root*21, mid1, r, L, R));return ret;}int maxProfitAssignment(vectorint difficulty, vectorint profit, vectorint worker) {int ret 0;mapint, int pf;for (int i 0; i difficulty.size(); i) {if (pf.find(difficulty[i]) pf.end()) {pf[difficulty[i]] profit[i];}else {pf[difficulty[i]] max(pf[difficulty[i]], profit[i]);}}tree.resize(400004, 0);int N tree.size()-1;for (auto it pf.begin(); it ! pf.end(); it) {updateTree(1, 1, N, it-first, it-second);}for (int i 0; i worker.size(); i) {ret getMax(1, 1, N, 1, worker[i]);}return ret;}
};随后查看了题解明确了重点是【找到小于等于某个难度值能得到的最大收益】其实与之相应的之前线段树的方法里的查询区间左区间固定为1也就是需要的信息只有右区间
首先工人是无法完成难度大于他能力的任务的所以先将任务按难度排序。随后设arr[i]表示【能力为i的工人完成任务能得到的最大收益】。于是在两个任务难度之间的arr[i]都是相同的。但是要保证arr[]的元素都是递增的也就是花费了更多的能力不能使得到的收益变少。也就是考虑到【A任务难度大于B任务但收益小于B任务】的情况。因此添加一个对比保证递增。 int arr[100001] {};int pos jbs[0].first;int last_pro 0;for (int i 1; i jbs.size(); i) {int now_diff jbs[i].first;int tmp_pro max(last_pro, jbs[i-1].second);while (pos now_diff) {arr[pos] tmp_pro;}last_pro tmp_pro;}而能力比最难的任务大的工人能得到的收益也是最大的。 last_pro max(last_pro, jbs.back().second);while (pos *max_element(worker.begin(), worker.end())) {arr[pos] last_pro;}最后将能得到的收益相加即可。
完整代码
bool cmp(pairint, int x, pairint, int y) {return x.first y.first;
}class Solution {
public:int maxProfitAssignment(vectorint difficulty, vectorint profit, vectorint worker) {vectorpairint, int jbs;for (int i 0; i difficulty.size(); i)jbs.push_back(make_pair(difficulty[i], profit[i]));sort(jbs.begin(), jbs.end(), cmp);int arr[100001] {};int pos jbs[0].first;int last_pro 0;for (int i 1; i jbs.size(); i) {int now_diff jbs[i].first;int tmp_pro max(last_pro, jbs[i-1].second);while (pos now_diff) {arr[pos] tmp_pro;}last_pro tmp_pro;}last_pro max(last_pro, jbs.back().second);while (pos *max_element(worker.begin(), worker.end())) {arr[pos] last_pro;}int ret 0;for (int i 0; i worker.size(); i) {ret arr[worker[i]];}return ret;}
};
