মনে করুন, একটি কোম্পানি A তার আইপিও শীঘ্রই শুরু করতে চায়। শেয়ারের ভালো দাম পেতে A কিছু প্রজেক্টে কাজ করে ক্যাপিটাল বাড়াতে চায়। A সীমিত রিসোর্সের কারণে আইপিওর আগে সর্বোচ্চ kটি প্রজেক্ট সম্পন্ন করতে পারে। সর্বোচ্চ ক্যাপিটাল বাড়াতে কোন প্রজেক্টগুলো বেছে নেওয়া উচিত তা বের করতে হবে।
প্রতিটি প্রজেক্ট i-র लिये পিউর প্রফিট Pi এবং মিনিমাম ক্যাপিটাল Ci দরকার। প্রাথমিক ক্যাপিটাল W। প্রজেক্ট শেষ করলে প্রফিট ক্যাপিটালে যোগ হবে। সর্বোচ্চ kটি প্রজেক্ট বেছে নিয়ে চূড়ান্ত ক্যাপিটাল সর্বোচ্চ করুন।
যেমন, k=2, W=0, profit=[1,2,4], capital=[0,1,1] হলে, আউটপুট ৫। প্রথমে প্রজেক্ট ০ (ক্যাপিটাল ০), প্রফিট ১ পাওয়া যায়। তারপর প্রজেক্ট ২ (ক্যাপিটাল ১), প্রফিট ৪ পাওয়া যায়। মোট ০+১+৪=৫।
সমাধানের ধাপসমূহ
- দুটি প্রায়োরিটি কিউ: pqCapital (ক্যাপিটাল অনুযায়ী), pqMain (প্রফিট অনুযায়ী)
- সকল প্রজেক্ট pqCapital-এ ঢুকান
- i := 0 থেকে k-1 পর্যন্ত:
- যখন pqCapital খালি নয় এবং টপের ক্যাপিটাল <= W: টপকে pqMain-এ সরান
- যদি pqMain খালি হয়, ব্রেক
- W += pqMain.top().first, pqMain.pop()
- W রিটার্ন করুন
উদাহরণ
#include <bits/stdc++.h> using namespace std; struct Comparator{ bool operator() (pair <int, int> a, pair <int, int> b){ return !(a.second < b.second); } }; class Solution { public: int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) { priority_queue < pair <int, int>, vector < pair <int, int> >, Comparator> pqCapital; priority_queue < pair <int ,int> > pqMain; int n = Profits.size(); for(int i = 0; i < n; i++){ pqCapital.push({Profits[i], Capital[i]}); } for(int i = 0; i < k; i++){ while(!pqCapital.empty() && pqCapital.top().second <= W){ pqMain.push(pqCapital.top()); pqCapital.pop(); } if(pqMain.empty()) break; W += pqMain.top().first; pqMain.pop(); } return W; } }; main(){ Solution ob; vector<int> v = {1,2,4}, v1 = {0,1,1}; cout << (ob.findMaximizedCapital(2,0, v, v1)); }
ইনপুট
আউটপুট
5
