สมมุติว่ามีวิศวกร n คน พวกมันมีหมายเลขตั้งแต่ 1 ถึง n และเรายังมีอาร์เรย์สองชุด:ความเร็วและประสิทธิภาพ โดยที่ speed[i] และ ประสิทธิภาพ[i] แสดงถึงความเร็วและประสิทธิภาพสำหรับวิศวกร ith เราต้องค้นหาประสิทธิภาพสูงสุดของทีมที่ประกอบด้วยวิศวกรมากที่สุด k คน คำตอบอาจมีขนาดใหญ่มาก ให้คืนค่าเป็นโมดูโล 10^9 + 7.
ประสิทธิภาพของทีมคือผลรวมของความเร็วของวิศวกรคูณด้วยประสิทธิภาพขั้นต่ำของวิศวกร
ดังนั้น หากอินพุตเป็น n =6 ความเร็ว =[1,5,8,2,10,3] ประสิทธิภาพ =[9,7,2,5,4,3] k =2 แล้วผลลัพธ์ จะเท่ากับ 60 เนื่องจากเรามีสมรรถนะสูงสุดของทีมโดยคัดเลือกวิศวกรที่มีความเร็ว 10 และประสิทธิภาพ 4 และวิศวกรที่มีความเร็ว 5 และประสิทธิภาพ 7 กล่าวคือ ประสิทธิภาพ =(10 + 5) * นาที (4, 7) =60 .
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ยกเลิก :=0
-
กำหนดอาร์เรย์ 2 มิติ v
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
ใส่ { e[i], s[i] } ต่อท้าย v
-
-
เรียงลำดับอาร์เรย์ v ในลำดับย้อนกลับ
-
กำหนดลำดับความสำคัญหนึ่งคิว pq
-
ผลรวม :=0
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
ถ้าขนาดของ pq เท่ากับ k แล้ว −
-
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
