ধরুন এন ইঞ্জিনিয়ার আছে৷ তারা 1 থেকে n পর্যন্ত সংখ্যাযুক্ত এবং আমাদের দুটি অ্যারে রয়েছে:গতি এবং দক্ষতা, এখানে গতি[i] এবং দক্ষতা [i] ith ইঞ্জিনিয়ারের জন্য গতি এবং দক্ষতার প্রতিনিধিত্ব করে। আমাদের বেশিরভাগ কে ইঞ্জিনিয়ারদের সমন্বয়ে গঠিত একটি দলের সর্বাধিক কর্মক্ষমতা খুঁজে বের করতে হবে। উত্তরটি খুব বড় হতে পারে তাই এটি মডিউল 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 .
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ret :=0
-
একটি 2D অ্যারে v
সংজ্ঞায়িত করুন -
আরম্ভ করার জন্য i :=0, যখন i
-
v
এর শেষে { e[i], s[i] } ঢোকান
-
-
অ্যারে v কে বিপরীত ক্রমে সাজান
-
একটি অগ্রাধিকার সারি pq
সংজ্ঞায়িত করুন -
যোগফল :=0
-
আরম্ভ করার জন্য i :=0, যখন i
-
যদি pq এর আকার k এর সমান হয়, তাহলে −
-
যোগফল :=যোগফলের শীর্ষ উপাদান - pq
-
pq
থেকে উপাদান মুছুন
-
-
যোগফল :=যোগফল + v[i, 1]
-
pq
-এ v[i, 1] ঢোকান -
ret :=ret এর সর্বোচ্চ এবং যোগফল * v[i, 0]
-
-
রিটার্ন মোড (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
