C++ এ তাদের কর্মক্ষমতার উপর ভিত্তি করে কর্মচারীদের যে চূড়ান্ত পরিমাণ অর্থ প্রদান করা উচিত তা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে পারফরম্যান্স এবং খরচ নামে একই দৈর্ঘ্যের সংখ্যার দুটি তালিকা রয়েছে। এবং আমাদের আরও একটি সংখ্যা k আছে। এগুলি নির্দেশ করে যে প্রতিটি কর্মী আমি কর্মক্ষমতা [i] স্তরে সম্পাদন করি এবং এটির জন্য কমপক্ষে খরচ লাগে[i]। আমাদের k কর্মচারীদের নিয়োগের ন্যূনতম খরচ খুঁজে বের করতে হবে যে কর্মীদের তাদের কর্মক্ষমতার সাথে গ্রুপের অন্যান্য কর্মীদের তুলনায় আনুপাতিকভাবে বেতন দেওয়া হবে।

সুতরাং, যদি ইনপুটটি কর্মক্ষমতা =[5, 3, 2] খরচ =[100, 5, 4] k =2 এর মত হয়, তাহলে আউটপুট হবে 10, যেমন আমরা emp1 এবং emp2 নির্বাচন করতে পারি। তাদের অবশ্যই কমপক্ষে 5 + 4 =9 পরিমাণ অর্থ প্রদান করতে হবে। কিন্তু emp1 emp2 থেকে 1.5 গুণ ভালো পারফর্ম করে, তাই তাকে কমপক্ষে 1.5 * 4 =6 দিতে হবে। তাই মোট তারা 6 + 4 =10 পাবে।

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

• n :=c

  এর আকার

• n

  আকারের একটি অ্যারে সেক সংজ্ঞায়িত করুন

• 0 থেকে n−1

  মান দিয়ে seq পূরণ করুন

• এই মানদণ্ডের উপর ভিত্তি করে অ্যারে সেক সাজান (c[i] * p[j]

• উত্তর :=inf, psum :=0

• একটি অগ্রাধিকার সারি সংজ্ঞায়িত করুন pq

• আরম্ভ করার জন্য i :=0, যখন i

  • idx :=seq[i]

  • pq

    -এ p[idx] ঢোকান

  • psum :=psum + p[idx]

  • যদি pq> k এর আকার হয়, তাহলে −

    • psum :=psum − pq

      এর শীর্ষ উপাদান

    • pq

      থেকে শীর্ষ উপাদান মুছুন

  • যদি i>=k − 1, তাহলে −

    • উত্তর :=সর্বনিম্ন উত্তর এবং (c[idx] / p[idx] * psum)

• উত্তর ফেরত দিন

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

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
double solve(vector<int>& p, vector<int>& c, int k) {
   int n = c.size();
   vector<int> seq(n);
   for (int i = 0; i < n; ++i)
   seq[i] = i;
   sort(seq.begin(), seq.end(), [&](int i, int j) { return c[i] *
   p[j] < c[j] * p[i]; });
   double ans = INT_MAX, psum = 0;
   priority_queue<int> pq;
   for (int i = 0; i < n; ++i) {
      int idx = seq[i];
      pq.emplace(p[idx]);
      psum += p[idx];
      if (pq.size() > k) {
         psum −= pq.top();
         pq.pop();
      }
      if (i >= k − 1)
      ans = min(ans, (double)c[idx] / p[idx] * psum);
   }
   return ans;
}
int main(){
   vector<int> performance = {5, 3, 2};
   vector<int> costs = {100, 5, 4};
   int k = 2;
   cout << solve(performance, costs, k);
}

ইনপুট

{5, 3, 2}, {100, 5, 4}, 2

আউটপুট

10