有一些工作：difficulty[i] 表示第i个工作的难度，profit[i]表示第i个工作的收益。
现在我们有一些工人。worker[i]是第i个工人的能力，即该工人只能完成难度小于等于worker[i]的工作。
每一个工人都最多只能安排一个工作，但是一个工作可以完成多次。
举个例子，如果3个工人都尝试完成一份报酬为1的同样工作，那么总收益为 $3。如果一个工人不能完成任何工作，他的收益为 $0 。
我们能得到的最大收益是多少？
示例：
输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], workers = [4,5,6,7] 输出: 100 解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。提示:
1 <= difficulty.length = profit.length <= 10000 1 <= worker.length <= 10000 difficulty[i], profit[i], worker[i] 的范围是 [1, 10^5]思 路 分 析 ： \color{blue}思路分析： 思路分析：对于每一个工人我们总是想能获取他的最大收益，这样才能达到整体最大。蛋式也有一个限制条件，就是分配的工作的难度不能超过工人的能力范围。因此摆在我们面前的有两个问题：第一，如何获取这个功能能够胜任的最大难度的工作difficulty[i]，第二，如何确定[0, difficulty[i]]在此难度区间之内（即这名工人能够胜任的工作）中利润最大工作。
对于第一个问题，我们可以先将difficulty进行升序排序（注意移动了difficulty则必须要同时移动它在profit数组对应的利润的位置），然后使用二分法，这样就能找到每一个工人可胜任的工作区间[0, left]
对于第二个问题，我们可以采用一个数组maxProfitVec，maxProfitVec[i]表示在升序排列的difficulty中前i个工作中获利大的利润。
这样两个问题就迎刃而解了。
class Solution { public: int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& workers) { int profitSize = profit.size(), maxResSum = 0; vector<pair<int, int>> myVec(profitSize); //第一步：按照{difficulty[i], profit[i]}进行捆绑 for (int i = 0; i < profitSize; ++i){ myVec[i] = { difficulty[i], profit[i] }; } //第二步：按照难度进行升序排序 sort(myVec.begin(), myVec.end(), myCmp); vector<int> maxProfitVec(profitSize + 1, 0);//maxProfitVec[i]记录前i个工作中可获得大的利润 //第三步：递推求解前i个工作中获利大的利润 for (int i = 1; i <= profitSize; ++i){ maxProfitVec[i] = max(maxProfitVec[i - 1], myVec[i - 1].second); } //第四步：求出每个工人可获取的最大利润 for (const auto &worker : workers){ //二分法，寻找[0, left]left为这个工人可获胜任的最大难度的工作的边界 int left = 0, right = profitSize - 1, mid; while (left < right){ mid = (left + right) / 2; if (myVec[mid].first > worker){ //如果myVec[mid]的难度超过了工人的能力，则myVec[mid, right]的工作都不能胜任 right = mid - 1; } else{//如果myVec[mid]的难度不超过工人的能力，则myVec[left, mid]的工作都能胜任 left = mid + 1; } } //退出循环后myVec[left].first指向的就是这名工人最大可胜任的工作难度 //注意边界修正问题，left是下标，而maxProfitVec[i]是表示前i个工作的最大利润 if (myVec[left].first <= worker) { left += 1; } maxResSum += maxProfitVec[left]; } return maxResSum; } //按照难度升序排序 static bool myCmp(const pair<int, int> &pairOne, const pair<int, int> &pairTwo){ return pairOne.first < pairTwo.first; } };