โปรแกรม C++ หาจำนวนพนักงานแต่ละระดับทักษะที่ต้องโอนไปสาขาใหม่

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

สมมติว่ามีพนักงาน n คนในบริษัท แต่ละคนมีระดับทักษะ 1 ถึง k จำนวนพนักงานระดับ i อยู่ในอาร์เรย์ skill โดย skill[i] คือจำนวนพนักงานระดับ i สาขาใหม่เปิด ต้องโอนพนักงานทักษะต่างๆ ไป m คน ต้องหาวิธีโอนที่ลดสูตร max(branch[i]/m - skill[i]/n) ต่ำสุด ผลรวม branch[i] = m ต้องหาค่า branch[i]

ตัวอย่าง: k = 5, n = 10, m = 25, skill = {5, 3, 2, 7, 4} ผลลัพธ์คือ 12 7 5 17 10

ขั้นตอนการแก้ปัญหา

sum := 0
สำหรับ i := 0 ถึง k-1:
    skill[i] := skill[i] * m / n
กำหนดอาร์เรย์คู่ a
สำหรับ i := 0 ถึง k-1:
    c := skill[i]
    sum := sum + c
    a[i].first := skill[i] - c
    a[i].second := i
เรียงลำดับ a
กลับลำดับ a
สำหรับ i := 0 ถึง m - sum - 1:
    skill[a[i].second] := skill[a[i].second] + 1
สำหรับ i := 0 ถึง k-1:
    พิมพ์ skill[i]

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

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

const int INF = 1e9;
void solve(int k, int n, int m, vector<double> skill){
    int sum = 0;
    for (int i = 0; i < k; i++) skill[i] = skill[i] * m / n;
    vector<pair<double, int>> a(k);
    for (int i = 0; i < k; i++) {
        int c = skill[i];
        sum += c;
        a[i].first = skill[i] - c;
        a[i].second = i;
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    for (int i = 0; i < m - sum; i++) {
        skill[a[i].second] += 1;
    }
    for (int i = 0; i < k; i++) {
        if (i != k - 1) cout << int(skill[i]) << " ";
        else cout << int(skill[i]) << endl;
    }
}

int main() {
    int k = 5, n = 10, m = 25;
    vector<double> skill = {5, 3, 2, 7, 4};
    solve(k, n, m, skill);
    return 0;
}

อินพุต

5, 10, 25, {5, 3, 2, 7, 4}

เอาต์พุต

12 7 5 17 10