n ইঞ্জিনিয়ার, speed[] এবং efficiency[] অ্যারে। সর্বোচ্চ k জন ইঞ্জিনিয়ার নিয়ে টিম বানাতে হবে। পারফরম্যান্স = (স্পিড যোগফল) × (মিনিমাম ইফিশিয়েন্সি)। মডুলো ১০^৯+৭।
উদাহরণ: n=6, speed=[1,5,8,2,10,3], efficiency=[9,7,2,5,4,3], k=2 -> ৬০ (ইঞ্জিনিয়ার ১০+৫ স্পিড, মিন ইফিশিয়েন্সি ৪) = ১৫×৪=৬০।
সমাধানের ধাপসমূহ
- ইঞ্জিনিয়ারদের (efficiency, speed) পেয়ারে রেখে efficiency অনুযায়ী ডিক্রিজিং সর্ট করুন।
- Min-heap (priority_queue) দিয়ে টপ k স্পিড মেইন্টেইন করুন।
- প্রতিটি ইঞ্জিনিয়ারকে মিনিমাম ইফিশিয়েন্সি ধরে রান করুন: sum += speed, heap.push(speed)। যদি heap.size() > k, sum -= heap.top(), heap.pop()।
- ret = max(ret, sum * efficiency)।
- ret % (1e9+7) রিটার্ন করুন।
C++ কোড উদাহরণ
#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);
}
};
int 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);
return 0;
}
ইনপুট
6, {1,5,8,2,10,3}, {9,7,2,5,4,3}, 2
আউটপুট
60
