Có n nhân viên, cấp độ 1..k. Mảng skill[i] = số nhân viên cấp i. Cần chuyển m nhân viên sang chi nhánh mới, mảng branch[i] số nhân viên cấp i chuyển đi (tổng = m). Tối thiểu hóa max(branch[i]/m - skill[i]/n).
Ví dụ
Với k=5, n=10, m=25, skill={5,3,2,7,4}, đầu ra 12 7 5 17 10.
Giải thuật
Tính mục tiêu lý tưởng: skill[i] * m / n. Lấy phần nguyên làm giá trị ban đầu. Tính phần dư (thực - nguyên). Sắp xếp phần dư giảm dần. Phân bổ m - sum nhân viên còn lại cho các cấp độ phần dư lớn nhất. In kết quả.
Mã C++
#include <bits/stdc++.h>
using namespace std;
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;
}
Đầu vào / Đầu ra
Input: 5, 10, 25, {5, 3, 2, 7, 4}
Output: 12 7 5 17 10