โปรแกรมหาจำนวนเงินสุดท้ายที่ควรจ่ายให้กับพนักงานตามผลงานในภาษา 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

• เติม seq ด้วยค่า 0 ถึง n-1

• เรียงลำดับอาร์เรย์ตามเกณฑ์เหล่านี้ (c[i] * p[j]

• ตอบ :=inf, psum :=0

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

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

  • idx :=seq[i]

  • แทรก p[idx] ลงใน pq

  • psum :=psum + p[idx]

  • ถ้าขนาดของ pq> k แล้ว −

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

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

  • ถ้า i>=k − 1 แล้ว −

    • ans :=ขั้นต่ำของ ans และ (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