数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中最大利润分配工作
假设我们有一些工作，difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的利润。现在假设我们有一些工人，worker[i] 表示第 i 个工人的能力，这意味着这个工人只能完成难度最多为 worker[i] 的工作。每个工人最多只能完成一项工作，但一项工作可以被多次完成。我们需要找到我们能够获得的最大利润是多少？
例如，如果输入像 difficulty = [2,4,6,8,10] 和 profit = [10,20,30,40,50] 以及 worker = [4,5,6,7]，则输出将为 100。因此，工人可以分配工作难度 [4,4,6,6]，获得的利润 [20,20,30,30]，总共为 100。
为了解决这个问题，我们将遵循以下步骤：
- ans := 0 且 n := profit 数组的大小
- 对 worker 数组进行排序
- 创建一个名为 v 的对列表
- 对于 i 从 0 到 n – 1，
- 将对 (difficulty[i], profit[i]) 插入 v 中
- 对 v 数组进行排序
- maxVal := 0，m := worker 数组的大小，j := 0
- 对于 i 从 0 到 m – 1
- 当 j < n 且 v[j] 的第一个值 <= worker[i] 时
- maxVal := maxVal 和 v[j] 的第二个值的较大值
- 将 j 增加 1
- ans := ans + maxVal
- 当 j < n 且 v[j] 的第一个值 <= worker[i] 时
- 返回 ans
让我们看看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
int ans = 0;
sort(worker.begin(), worker.end());
vector < pair <int, int> > v;
int n = profit.size(); // Number of jobs
for(int i = 0; i < n; i++){
v.push_back({difficulty[i], profit[i]});
}
sort(v.begin(), v.end());
int maxVal = 0;
int m = worker.size(); // Number of workers
int j = 0;
for(int i = 0; i < m; i++){
while(j < n && v[j].first <= worker[i]){
maxVal = max(maxVal, v[j].second);
j++;
}
ans += maxVal;
}
return ans;
}
};
int main() {
Solution ob1;
vector<int> difficulty{2,4,6,8,10};
vector<int> profit{10,20,30,40,50};
vector<int> worker{4,5,6,7};
cout << ob1.maxProfitAssignment(difficulty, profit, worker) << endl;
return 0;
}输入
[2,4,6,8,10]
[10,20,30,40,50]
[4,5,6,7]
vector<int> difficulty{2,4,6,8,10};
vector<int> profit{10,20,30,40,50};
vector<int> worker{4,5,6,7};输出
100
更新于: 2020年4月30日
303 次查看
广告