C++でK人の労働者を雇うための最小コストを求めるアルゴリズム

N人の労働者がいると仮定します。各労働者には作業の「質（quality）」を表すパラメータが割り当てられており、i番目の労働者は質 quality[i] と最低賃金の希望額 wage[i] を持っています。ここで、K人の労働者を雇って賃金支払いグループを結成することを考えます。K人のグループを雇用する際には、次の2つのルールを守る必要があります。

• グループ内の各労働者への支払いは、グループ内の他のメンバーと比較した質の比率に比例していなければなりません。
• グループ内のすべての労働者には、少なくともそれぞれの最低賃金の希望額以上を支払わなければなりません。

私たちの目的は、これらの条件を満たすグループを結成するために必要な最小の費用を求めることです。

例として、quality = [10, 22, 5]、wage = [70, 52, 30]、K = 2 が与えられた場合を考えてみましょう。このとき出力は 105.000 となります。1人目の労働者に70を、3人目の労働者に35を支払うことで、すべての条件を満たすことができるからです。

解法のアプローチ

この問題は、「比率によるソート」と「優先度付きキュー（ヒープ）」を組み合わせた貪欲法で効率的に解くことができます。手順は以下の通りです。

1. 質 q、賃金 w、比率 r（= w / q）をメンバに持つ構造体 Data を定義します。
2. n を quality のサイズとします。
3. サイズ n の Data 型配列 v を作成します。
4. i = 0 から n - 1 まで繰り返します。
   • v[i].q に quality[i] を代入します。
   • v[i].w に wage[i] を代入します。
   • v[i].r に v[i].w / v[i].q を代入します。
5. 配列 v を r の値で昇順にソートします。
6. sum := 0、ans := 無限大（十分に大きな値）と初期化します。
7. 最大値を取り出せる優先度付きキュー pq を用意します。
8. i = 0 から n - 1 まで繰り返します。
   • pq のサイズが k と等しい場合：pq の先頭（最も大きい質）を x として取り出し、sum から x を引いて pq から削除します。
   • pq のサイズが k - 1 と等しい場合：ans を min(sum × v[i].r + v[i].w, ans) で更新します。
   • sum に v[i].q を加算し、v[i].q を pq に挿入します。
9. ans を返します。

なぜこの方法が機能するのか

ポイントは、労働者を「時給換算の比率 r = 賃金 ÷ 質」の小さい順に並べるところにあります。ある労働者 i を基準（グループ内で最も高い比率の人物）として採用すると、ソート済み配列で i より前にいる労働者の比率はすべて r_i 以下であるため、全員を比率 r_i で比例払いしても最低賃金の条件を満たします。このとき総支払額は「r_i × グループ全体の質の合計」で表されるため、基準となる労働者を固定できれば、あとは質の合計が最小になるように残りの K - 1 人を選べばよいことになります。最大ヒープを使って質の大きな候補から順に追い出すことで、常に「質の合計が最小の K - 1 人」を維持できる仕組みです。

計算量は、ソートに O(n log n)、各労働者ごとのヒープ操作に O(log k) ずつかかるため、全体で O(n log n) となり、非常に効率的です。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
struct Data {
    double q, w, r;
};
class Solution {
    public:
    static bool cmp(Data a, Data b) { return a.r < b.r; }
    double mincostToHireWorkers(vector<int> &quality, vector<int> &wage, int k) {
        int n = quality.size();
        vector<Data> v(n);
        for (int i = 0; i < n; i++) {
            v[i].q = quality[i];
            v[i].w = wage[i];
            v[i].r = v[i].w / v[i].q;
        }
        sort(v.begin(), v.end(), cmp);
        double sum = 0;
        double ans = INT_MAX;
        priority_queue<int> pq;
        for (int i = 0; i < n; i++) {
            if (pq.size() == k) {
                double x = pq.top();
                sum -= x;
                pq.pop();
            }
            if (pq.size() == k - 1) {
                ans = min((sum * v[i].r) + v[i].w, ans);
            }
            sum += v[i].q;
            pq.push(v[i].q);
        }
        return ans;
    }
};
main() {
    Solution ob;
    vector<int> v = {10, 22, 5}, v1 = {70, 52, 30};
    cout << (ob.mincostToHireWorkers(v, v1, 2));
}

入力

{10,22,5}
{70,52,30}
2

出力

105