C++ এ আইপিও

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

ধরুন আমাদের বেশ কিছু প্রজেক্ট আছে। প্রতিটি প্রকল্পের জন্য, এটির একটি বিশুদ্ধ লাভ পাই রয়েছে এবং সংশ্লিষ্ট প্রকল্পটি শুরু করার জন্য 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 :=লাভের আকার
• আরম্ভ করার জন্য i :=0, যখন i করুন
• pqCapital-এ { মুনাফা[i], মূলধন[i] } ঢোকান

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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