หาต้นทุนขั้นต่ำในการจ้างงาน k คนตามประสิทธิภาพและค่าใช้จ่ายใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะหา ต้นทุนขั้นต่ำ ในการจ้างงาน k พนักงาน โดยที่:

• พนักงาน i มี ประสิทธิภาพ performance[i]
• พนักงาน i ต้องได้ค่าจ้างอย่างน้อย costs[i]
• ค่าจ้างต้อง สัมพันธ์กับประสิทธิภาพ (ผู้ที่ประสิทธิภาพสูงกว่าได้ค่าจ้างมากกว่าตามสัดส่วน)

ตัวอย่าง

performance = [5, 3, 2], costs = [100, 5, 4], k = 2
Output: 10
เลือก emp1 (perf=5, cost=5) และ emp2 (perf=3, cost=4)
อัตราส่วน 5:3 → emp1 ได้ 1.5×emp2 → emp2 ได้ 4, emp1 ได้ 6 → รวม 10

อัลกอริทึม: Greedy + Priority Queue

1. เรียงพนักงานตาม อัตราส่วน cost/performance (ค่าใช้จ่ายต่อหน่วยประสิทธิภาพ) จากน้อยไปมาก
2. วนลูปตามลำดับที่เรียง:
   • เพิ่ม performance เข้า max-heap
   • รักษา performance รวม (psum) ของ k คนที่เลือก
   • ถ้า heap > k → ลบคนที่ performance สูงสุด (เพราะเราต้องการ psum น้อยที่สุด)
   • เมื่อมี ≥ k คน → คำนวณต้นทุน = (cost[i]/perf[i]) × psum
3. เลือกค่าต่ำสุด

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

double solve(vector& p, vector& c, int k) {
    int n = c.size();
    vector seq(n);
    for (int i = 0; i < n; ++i) seq[i] = i;
    
    // เรียงตาม cost/performance ratio (c[i]/p[i])
    sort(seq.begin(), seq.end(), [&](int i, int j) {
        return (long long)c[i] * p[j] < (long long)c[j] * p[i];
    });
    
    double ans = INT_MAX, psum = 0;
    priority_queue pq;  // max-heap เก็บ performance
    
    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 performance = {5, 3, 2};
    vector costs = {100, 5, 4};
    int k = 2;
    cout << solve(performance, costs, k);
    return 0;
}

ผลลัพธ์

10

คำอธิบาย

เรียงตาม cost/perf ratio: emp2(5/3≈1.67), emp3(4/2=2), emp1(100/5=20)
ลองเลือก emp2+emp3: ratio=2, psum=5, cost=2×5=10 ✓
ลองเลือก emp2+emp1: ratio=20, psum=8, cost=20×8=160 ✗

สรุป

Greedy เรียงตาม unit cost + max-heap รักษา k คนที่ performance รวมน้อยที่สุด หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ