ต้นทุนขั้นต่ำในการจ้างพนักงาน K ใน C++

สมมติว่ามีคนงาน N ผู้ปฏิบัติงานแต่ละคนมีพารามิเตอร์คุณภาพ พนักงานคนที่ i มีคุณภาพ[i] และค่าจ้างขั้นต่ำที่คาดหวัง[i] ตอนนี้เราต้องการจ้างคนงาน K เพื่อจัดตั้งกลุ่มที่ได้รับค่าจ้าง เมื่อเราจ้างคนงานกลุ่ม K เราต้องจ่ายตามกฎต่อไปนี้ -

• พนักงานแต่ละคนในกลุ่มที่ได้รับค่าจ้างควรได้รับค่าจ้างตามอัตราส่วนของคุณภาพโดยเปรียบเทียบกับคนอื่นๆ ในกลุ่มที่ได้รับค่าจ้าง

• คนงานทุกคนในกลุ่มที่ได้รับค่าจ้างต้องได้รับค่าจ้างอย่างน้อยตามที่คาดหวังไว้

เราต้องหาจำนวนเงินที่น้อยที่สุดที่จำเป็นในการจัดตั้งกลุ่มที่ได้รับค่าตอบแทนตามเงื่อนไขข้างต้น

ดังนั้น หากอินพุตมีคุณภาพเท่ากับ =[10,22,5] ค่าจ้าง =[70,52,30] และ K =2 ผลลัพธ์จะเป็น 105.000 เนื่องจากเราจะจ่าย 70 ให้กับคนงานคนแรกและ 35 คนให้กับคนงานคนที่ 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดข้อมูลด้วย q, w และ r

• n :=ขนาดของคุณภาพ

• สร้างอาร์เรย์ Data v ขนาด n

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • q ของ v[i] :=quality[i]

  • w ของ v[i] :=ค่าจ้าง[i]

  • r ของ v[i] :=w ของ v[i] /q ของ v[i]

• จัดเรียงอาร์เรย์ v ตามค่า r

• อุณหภูมิ :=0

• ผลรวม :=0

• ตอบ :=inf

• กำหนดลำดับความสำคัญหนึ่งคิว pq

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้าขนาดของ pq เท่ากับ k แล้ว −

    • x :=องค์ประกอบด้านบนของ pq

    • ผลรวม :=ผลรวม - x

    • ลบองค์ประกอบออกจาก pq

  • ถ้าขนาดของ pq เท่ากับ k - 1 แล้ว −

    • ans :=ขั้นต่ำของ (ผลรวม * r ของ v[i]) + w ของ v[i] และ ans

  • sum :=sum + q ของ v[i]

  • แทรก q ของ v[i] ลงใน pq

• กลับมาอีกครั้ง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
struct Data {
   double q, w, r;
};
class Solution {
   public:
   static bool cmp(Data a, Data b) { return a.r < b.r; }
   double mincostToHireWorkers(vector<int> &quality, vector<int>
   &wage, int k) {
      int n = quality.size();
      vector<Data> v(n);
      for (int i = 0; i < n; i++) {
         v[i].q = quality[i];
         v[i].w = wage[i];
         v[i].r = v[i].w / v[i].q;
      }
      sort(v.begin(), v.end(), cmp);
      double temp = 0;
      double sum = 0;
      double ans = INT_MAX;
      priority_queue<int> pq;
      for (int i = 0; i < n; i++) {
         if (pq.size() == k) {
            double x = pq.top();
            sum -= x;
            pq.pop();
         }
         if (pq.size() == k - 1) {
            ans = min((sum * v[i].r) + v[i].w, ans);
         }
         sum += v[i].q;
         pq.push(v[i].q);
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {10,22,5}, v1 = {70,52,30};
   cout << (ob.mincostToHireWorkers(v, v1, 2));
}

อินพุต

{10,22,5}
{70,52,30}
2

ผลลัพธ์

105