資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告