个人练习-Leetcode-826. Most Profit Assigning Work

题目链接：https://leetcode.cn/problems/most-profit-assigning-work/

题目大意：给出一串任务，difficulty表示任务难度，profit表示任务的收益（以下简称diff和pro）。给出一串工人的能力worker。每个工人只能做一个任务，且工人只能完成难度小于等于它能力的任务。同一人物可以完成多次。

思路：题目的关键是给每个工人找到【难度小于等于其能力的】【收益最大的】任务。

一开始的思路：暴力搜索，果不其然，寄了。。。

然后想到了前两天用过的线段树。先用一个map<int, int> pf记录某个diff能得到的最大的pro。这是为了当出现【多个任务难度相同收益却不同】的情况时，只记录收益最大的那个任务。因此，map的存储量应该是最小的。

线段树tree[]存的是【当前节点的区间内最大收益】。在初始化时，用updateTree()方法一一插入叶子节点，并且给每个非叶子节点记录左右儿子最大的收益。

随后，给每个工人，查询区间[1, worker[i]]内最大的收益。

几个例子在IDE里都通过了，但是leetcode里就是有heap-use-after-free的错误，查了查意思是引用了已经free掉的空间。然而我并没有debug出是哪里用了非法的空间。因此暂且先放这里。

线段树方法完整代码：

class Solution {
public:vector<int> tree;void updateTree(int root, int l, int r, int i, int val) {if (l == r) {tree[root] = val;return;}int mid = (l+r) / 2;if (i <= mid) {updateTree(root*2, l, mid, i, val);}else {updateTree(root*2+1, mid+1, r, i, val);}tree[root] = max(tree[root*2], tree[root*2+1]);}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 = (l+r)/2;if (L <= mid)ret = getMax(root*2, l, mid, L, R);if (R > mid)ret = max(ret, getMax(root*2+1, mid+1, r, L, R));return ret;}int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {int ret = 0;map<int, 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(pair<int, int> x, pair<int, int> y) {return x.first < y.first;
}class Solution {
public:int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {vector<pair<int, 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;}
};