C++-এ কর্মচারীদের পারফরম্যান্স অনুযায়ী দেয়া উচিত চূড়ান্ত পরিমাণ বের করা

মান লইয়া আমাদের দুটি লিস্ট আছে performance এবং costs একই দৈর্ঘ্যের। এবং আরেকটি নম্বর k। এগুলো ইঙ্গিত করে প্রতিটি কর্মী i performance[i] লেভেলে পারফর্ম করে এবং তাকে কমপক্ষে costs[i] টাকা লাগবে। আমাদের k জন কর্মী হায়ার করার মিনিমাম কস্ট বের করতে হবে যা প্রদত্ত যে কর্মীরা তাদের পারফরম্যান্স অনুপাতিকভাবে পেমেন্ট পাবে গ্রুপের অন্যান্য কর্মীর সাপেক্ষে।

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

এটি সমাধান করতে, আমরা এই ধাপগুলো ফলো করব:

n := c-এর সাইজ
size n-একটি seq অ্যারে ডিফাইন করুন
seq কে 0 থেকে n-1 মান দিয়ে ফিল করুন
seq অ্যারে সর্ট করুন এই ক্রাইটেরিয়া দিয়ে (c[i] * p[j] < c[j] * p[i])
ans := inf, psum := 0
একটি প্রায়োরিটি কিউ pq ডিফাইন করুন
i = 0 থেকে n-১ পর্যন্ত:
- idx := seq[i]
- p[idx] pq-তে পুশ করুন
- psum += p[idx]
- যদি pq-এর সাইজ > k হয়, তবে psum -= pq.top() এবং pq.pop()
- যদি i >= k-1 হয়, তবে ans = min(ans, (c[idx] / p[idx] * psum))
ans রিটার্ন করুন

বेहतर বোঝার জন্য ইমপ্লিমেন্টেশন দেখুন:

উদাহরণ

#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