C++でパフォーマンスに基づく従業員への支払額（最小雇用コスト）を求めるプログラム

同じ長さの2つの数値リスト「performance（業績）」と「costs（希望額）」、そして整数 k が与えられているとします。各従業員 i は performance[i] のレベルで業務を行い、少なくとも costs[i] の報酬を求めています。このとき、k 人の従業員を雇用するための最小コストを求めるのが課題です。ただし、採用された従業員は、グループ内の他のメンバーと比較した業績に比例して支払われるという条件が付きます。

たとえば、入力が performance = [5, 3, 2]、costs = [100, 5, 4]、k = 2 の場合、出力は 10 になります。従業員1と従業員2を採用すると、それぞれ最低でも 5 + 4 = 9 の支払いが必要です。しかし、従業員1の業績は従業員2の1.5倍であるため、少なくとも 1.5 × 4 = 6 を支払う必要があります。したがって、合計支払額は 6 + 4 = 10 となります。

解法のアプローチ

この問題は、「コスト÷業績」という比率で従業員を並べ替え、優先度付きキューを組み合わせることで効率的に解けます。具体的には、以下の手順に従います。

• n := 配列 c のサイズとする
• サイズ n の配列 seq を定義し、0 から n−1 までのインデックスを格納する
• 比較条件（c[i] * p[j] < c[j] * p[i]）に基づいて seq をソートする
• ans := 無限大、psum := 0 で初期化する
• 優先度付きキュー pq を定義する
• i := 0 から開始し、i < n の間、i を 1 ずつ増やしながら以下を繰り返す
  • idx := seq[i]
  • p[idx] を pq に挿入し、psum := psum + p[idx] とする
  • pq のサイズが k を超えたら、psum から pq の最大要素を減算し、その要素を pq から削除する
  • i >= k − 1 のとき、ans := min(ans, c[idx] / p[idx] * psum) を計算する
• 最後に ans を返す

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

従業員を「コスト／業績」の比率の昇順に並べると、走査中の任意の時点で、現在注目している従業員はそれまでに見た全員の中で最も高い支払率を持つことになります。つまり、この従業員を含む k 人のグループの総支払額は「現在の比率 × グループ全体の業績合計」で表されます。総支払額を最小化するには、業績の小さいメンバーを選べばよいため、最大ヒープ型の優先度付きキューで「これまでに登場した中で業績の小さい k 人」を常に維持しておけばよいのです。

C++での実装例

より深く理解するために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
double solve(vector<int>& p, vector<int>& c, int k) {
    int n = c.size();
    vector<int> seq(n);
    for (int i = 0; i < n; ++i)
        seq[i] = i;
    sort(seq.begin(), seq.end(), [&](int i, int j) {
        return c[i] * p[j] < c[j] * p[i];
    });
    double ans = INT_MAX, psum = 0;
    priority_queue<int> pq;
    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<int> performance = {5, 3, 2};
    vector<int> costs = {100, 5, 4};
    int k = 2;
    cout << solve(performance, costs, k);
}

入力

{5, 3, 2}, {100, 5, 4}, 2

出力

10

計算量

ソートに O(n log n)、優先度付きキューへの挿入・削除にそれぞれ O(log k) かかるため、全体の時間計算量は O(n log n) です。また、補助配列とキューのための空間計算量は O(n) となります。