সি++-এ আইপিও (IPO)

মান লিইয়ে নিই একটি কোম্পানি A শীঘ্রই তার আইপিও (IPO) শুরু করতে চায়। শেয়ারের ভালো দাম পাওয়ার জন্য B-কে, A আইপিওর আগে কিছু প্রজেক্টে কাজ করে তার ক্যাপিটাল বাড়াতে চায়। A-এর সীমিত রিসোর্স রয়েছে, সে আইপিওর আগে সর্বোচ্চ kটি স্বতন্ত্র প্রজেক্ট ফিনিশ করতে পারে। কি আপনি A-কে সাহায্য করতে পারেন, সর্বোচ্চ kটি স্বতন্ত্র প্রজেক্ট ফিনিশ করে তার মোট ক্যাপিটাল সর্বোচ্চ করার সেরা উপায় ডিজাইন করে?

মান লিইয়ে নিই বেশ কিছু প্রজেক্ট রয়েছে। প্রতিটি প্রজেক্ট i-র জন্য, এর একটি পিউর প্রফিট Pi রয়েছে এবং соответствующий প্রজেক্ট শুরু করার জন্য ন্যূনতম ক্যাপিটাল Ci প্রয়োজন। প্রথমে আমাদের W ক্যাপিটাল রয়েছে। যখন আমরা একটি প্রজেক্ট ফিনিশ করি, আমরা এর পিউর প্রফিট পাই এবং প্রফিটটি আমাদের মোট ক্যাপিটালে যোগ হয়।

সংক্ষেপে, দেওয়া প্রজেক্ট লিস্ট থেকে সর্বোচ্চ kটি স্বতন্ত্র প্রজেক্ট বেছে নিন যাতে আমাদের চূড়ান্ত ক্যাপিটাল সর্বোচ্চ হয়, এবং চূড়ান্ত সর্বোচ্চ ক্যাপিটাল আউটপুট করুন।

সুতরাং যদি ইনপুট হয় - k = 2, W = 0, প্রফিট লিস্ট [1,2,4], ক্যাপিটাল [0,1,1], তবে আউটপুট হবে 5। কারণ, শুরুতে আমাদের ক্যাপিটাল 0, তাই আমরা ইন্ডেক্স 0-এর প্রজেক্ট শুরু করতে পারি, সেটি থেকে প্রফিট 1 পাব, তাই ক্যাপিটাল হবে 1। ক্যাপিটাল 1 থাকলে, আমরা ইন্ডেক্স 1 বা 2-এর প্রজেক্ট শুরু করতে পারি, আমরা ইন্ডেক্স 2-কে বেছে নেব আরও প্রফিট পাওয়ার জন্য, তাই চূড়ান্ত উত্তর হবে 0 + 1 + 4 = 5।

समाधान पद्धति

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• দুটি প্রায়োরিটি কিউ pqCapital এবং pqMain তৈরি করুন
• n := Profits-এর আকার
• i := 0 থেকে आरंभ করুন, जब i < n, আপডেট করুন (i 1 বাড়ান), করুন:
  • { Profits[i], Capital[i] } কে pqCapital-এ ইনসার্ট করুন
• i := 0 থেকে आरंभ করুন, जब i < k, আপডেট করুন (i 1 বাড়ান), করুন:
  • যতক্ষণ (pqCapital খালি নয় এবং pqCapital-এর টপ এলিমেন্টের দ্বিতীয় মান <= W), করুন:
    • pqCapital-এর টপ এলিমেন্ট কে pqMain-এ ইনসার্ট করুন
    • pqCapital থেকে উপাদান মুছুন
  • যদি pqMain খালি হয়, তবে:
    • লুপ থেকে বের হোন
  • W := W + pqMain-এর টপ এলিমেন্টের প্রথম মান
  • pqMain থেকে উপাদান মুছুন
• 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)); }

इनपुट

2 0 [1,2,4] [0,1,1]

आउटपुट

5