ต้นทุนต่ำสุดในการจ้าง K คนใน C++

คำอธิบายปัญหา

มีคน N คน คนที่ i มี quality[i] และค่าจ้างขั้นต่ำ wage[i] จ้าง K คน จ่ายค่าจ้างสัดส่วน quality และต้อง ≥ wage[i] หาต้นทุนรวมน้อยที่สุด

ตัวอย่าง

quality=[10,22,5], wage=[70,52,30], K=2 → Output: 105
จ้างคน 0 และ 2: อัตรา = max(70/10, 30/5) = 7 → จ่าย 70+35=105

ข้อสังเกตสำคัญ

อัตราค่าจ้างต่อ quality (ratio = wage/quality) ต้อง ≥ ratio ของทุกคนในกลุ่ม
→ เลือกคนที่มี ratio ต่ำสุดเป็น "ผู้นำ" แล้วเลือก K-1 คนที่ quality ต่ำสุดจากคนที่ ratio ≤ ผู้นำ

แนวทางแก้ปัญหา: Sort by Ratio + Max Heap

1. คำนวณ ratio = wage/quality สำหรับแต่ละคน
2. เรียงคนตาม ratio เพิ่ม
3. วนคนตาม ratio (คนปัจจุบันเป็น "ผู้นำ" อัตราสูงสุดในกลุ่ม):
   • เก็บ quality ใน max heap
   • ถ้า heap size > K: pop quality สูงสุด (ลด sum quality)
   • ถ้า heap size == K: คำนวณ cost = sum_quality × ratio_current + wage_current

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

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

struct Worker { double q, w, r; };

class Solution {
    static bool cmp(Worker a, Worker b) { return a.r < b.r; }
    
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        int n = quality.size();
        vector<Worker> v(n);
        for(int i=0; i