資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++團隊最大效能
假設有n名工程師，編號從1到n，我們還有兩個陣列：speed和efficiency，其中speed[i]和efficiency[i]分別代表第i位工程師的速度和效率。我們必須找到由最多k名工程師組成的團隊的最大效能。答案可能非常大，因此返回它對10^9 + 7取模的結果。
這裡，團隊的效能是其工程師速度之和乘以其工程師中最低效率的結果。
因此，如果輸入類似於n = 6，speed = [1,5,8,2,10,3]，efficiency = [9,7,2,5,4,3]，k = 2，則輸出將為60，因為我們透過選擇速度為10且效率為4的工程師以及速度為5且效率為7的工程師來獲得團隊的最大效能。也就是說，效能 = (10 + 5) * min(4, 7) = 60。
為了解決這個問題，我們將遵循以下步驟：
ret := 0
定義一個二維陣列v
for 初始化 i := 0，當 i < n，更新（i 加 1），執行：
將 {e[i], s[i]} 插入到v的末尾
反向排序陣列v
定義一個優先佇列pq
sum := 0
for 初始化 i := 0，當 i < n，更新（i 加 1），執行：
如果pq的大小與k相同，則：
sum := sum - pq的頂部元素
從pq中刪除元素
sum := sum + v[i, 1]
將v[i, 1]插入到pq中
ret := ret和sum * v[i, 0] 的最大值
返回 ret mod (1^9 + 7)
讓我們看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxPerformance(int n, vector<int>& s, vector<int>& e, int k){
long long int ret = 0;
vector<vector<int> > v;
for (int i = 0; i < n; i++) {
v.push_back({ e[i], s[i] });
}
sort(v.rbegin(), v.rend());
priority_queue<int, vector<int>, greater<int> > pq;
long long int sum = 0;
for (int i = 0; i < n; i++) {
if (pq.size() == k) {
sum -= pq.top();
pq.pop();
}
sum += v[i][1];
pq.push(v[i][1]);
ret = max(ret, sum * v[i][0]);
}
return ret % (long long int)(1e9 + 7);
}
};
main(){
Solution ob;
vector<int> v = {1,5,8,2,10,3};
vector<int> v1 = {9,7,2,5,4,3};
cout << (ob.maxPerformance(6,v,v1,2));
}輸入
6, {1,5,8,2,10,3}, {9,7,2,5,4,3}, 2輸出
60
更新於：2020年6月9日
214 次瀏覽
廣告