সর্বাধিক সংখ্যক প্যাকেজ খুঁজে বের করার প্রোগ্রাম যা ক্রেতারা C++ এ কিনতে পারে

ধরুন আমাদের দুটি তালিকা বিক্রয় এবং ক্রেতা আছে। বিক্রয়ের প্রতিটি উপাদানের আকারে দুটি মান রয়েছে [দিন, মূল্য] এটি নির্দেশ করে যে প্যাকেজটি শুধুমাত্র সেই দিন প্রদত্ত মূল্যের জন্য বিক্রয়ের জন্য উপলব্ধ। এবং ক্রেতাদের প্রতিটি উপাদান [পে-ডে, পরিমাণ] ইঙ্গিত করে যে পে-ডে এবং তার পরে খরচ করার জন্য ক্রেতার সেই পরিমাণ অর্থ আছে। যদি প্রতিটি ক্রেতা সর্বাধিক একটি প্যাকেজ কিনতে পারে, এবং প্রতিটি প্যাকেজ শুধুমাত্র একজনের কাছে বিক্রি করা যেতে পারে, তাহলে সর্বাধিক সংখ্যক প্যাকেজ কেনা যাবে।

সুতরাং, যদি ইনপুট বিক্রয়ের মত হয় =[[0, 5], [0, 5], [0, 6], [1, 4], [1, 5], [3, 4]] ক্রেতা =[[ 0, 4], [0, 6], [1, 5]], তাহলে আউটপুট হবে 3, যেমন প্রথম ব্যক্তি প্যাকেজ নিতে পারে [1, 4]। দ্বিতীয় ব্যক্তি নিতে পারেন [0, 6]. এবং শেষ ব্যক্তিটি প্যাকেজটি নিতে পারে [1, 5]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

ret :=0
বেতন-দিবসের উপর ভিত্তি করে অ্যারে ক্রেতাদের সাজান, যদি পে-ডে একই হয় তাহলে তাদের পরিমাণের ভিত্তিতে সাজান
একটি সেট pq
সংজ্ঞায়িত করুন
অ্যারে বিক্রয় সাজান
i :=0
প্রতিটি আইটেমের জন্য এটি বিক্রয়-
- যখন (i <ক্রেতা এবং ক্রেতার আকার[i, 0] <=it[0]), করবেন −
  - পিকিউ
    -এ ক্রেতাদের[i, 1] সন্নিবেশ করান
  - (i 1 দ্বারা বাড়ান)
- j :=pq এর সূচী এটি [i] intp pq ঢোকাতে এবং এটিকে সাজাতে
- যদি j একটি বৈধ সূচক হয়, তাহলে −
  - (রেট 1 দ্বারা বৃদ্ধি করুন)
  - pq
    থেকে jth উপাদান মুছুন
রিটার্ন রিটার্ন

উদাহরণ

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

#include  namespace ব্যবহার করে std;class Solution { সর্বজনীন:static bool cmp(vector&a, vector&b) { ফেরত a[0] ==b[0 ]? a[1]> b[1] :a[0] >&বিক্রয়, ভেক্টর<ভেক্টর>&ক্রেতা) { int ret =0; sort(buyers.begin(), buyers.end()); মাল্টিসেট pq; sort(sales.begin(), sales.end(), cmp); int i =0; (স্বয়ংক্রিয় এবং এটি:বিক্রয়) { যখন (i >&sales, vector>&buyers) { return (new Solution())->solve(sales, buyers);}int main(){ ভেক্টর <ভেক্টর> বিক্রয় ={{0, 5},{0, 5},{0, 6},{1, 4},{1, 5},{3, 4}}; ভেক্টর<ভেক্টর> ক্রেতা ={{0, 4},{0, 6},{1, 5}}; cout <<সমাধান(বিক্রয়, ক্রেতা);

ইনপুট

<প্রে>{{0, 5},{0, 5},{0, 6},{1, 4},{1, 5},{3, 4}}, {{0, 4},{0 , 6},{1, 5}}