2462. 雇用K人の労働者の総コスト

2462. 雇佣 K 位工人的总代价 #

あなたには、0 から始まる整数配列costsが与えられます。costs[i]は、i 番目の労働者を雇うためのコストです。

同時に、2 つの整数kとcandidatesが与えられます。以下のルールに従って、ちょうど k 人の労働者を雇いたいと考えています。

k ラウンドの雇用を合計し、各ラウンドでちょうど 1 人の労働者を雇います。
各ラウンドの雇用では、最初の candidates 人と最後の candidates 人から、最小のコストの労働者を選びます。複数の労働者のコストが同じで最小の場合は、より小さいインデックスの労働者を選択します。
- 例えば、costs = [3,2,7,7,1,2]かつcandidates = 2の場合、最初のラウンドの雇用では、最小のコストの労働者である 4 番目の労働者を選択します。
- 2 番目のラウンドの雇用では、最小のコストであり、インデックスがより小さい 1 番目の労働者を選択します。注意：各ラウンドの雇用後、残りの労働者のインデックスが変わる可能性があります。
残りの労働者の数が candidates 人に満たない場合、次のラウンドでは最小のコストの労働者を選択します。複数の労働者のコストが同じで最小の場合は、より小さいインデックスの労働者を選択します。
各労働者は 1 回だけ選択できます。

ちょうど k 人の労働者を雇った場合の総コストを返します。

例 1：

入力：costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
出力：11
説明：合計で3人の労働者を雇います。最初の総コストは0です。
- 最初のラウンドの雇用では、[17,12,10,2,7,2,11,20,8]から選択します。最小のコストは2で、2人の労働者がいます。より小さいインデックスの3番目の労働者を選択します。総コストは0 + 2 = 2です。
- 2番目のラウンドの雇用では、[17,12,10,7,2,11,20,8]から選択します。最小のコストは2で、インデックスは4です。総コストは2 + 2 = 4です。
- 3番目のラウンドの雇用では、[17,12,10,7,11,20,8]から選択します。最小のコストは7で、インデックスは3です。総コストは4 + 7 = 11です。注意：インデックス3の労働者は、最初の4人と最後の4人の労働者の両方に含まれています。
総雇用コストは11です。

例 2：

入力：costs = [1,2,4,1], k = 3, candidates = 3
出力：4
説明：合計で3人の労働者を雇います。最初の総コストは0です。
- 最初のラウンドの雇用では、[1,2,4,1]から選択します。最小のコストは1で、2人の労働者がいます。より小さいインデックスの0番目の労働者を選択します。総コストは0 + 1 = 1です。注意：インデックス1と2の労働者は、最初の3人と最後の3人の労働者の両方に含まれています。
- 2番目のラウンドの雇用では、[2,4,1]から選択します。最小のコストは1で、インデックスは2です。総コストは1 + 1 = 2です。
- 3番目のラウンドの雇用では、3人未満の労働者がいるため、残りの労働者[2,4]から選択します。最小のコストは2で、インデックスは0です。総コストは2 + 2 = 4です。
総雇用コストは4です。

ヒント：

$1 <= costs.length <= 10^5$
$1 <= costs[i] <= 10^5$
$1 <= k, candidates <= costs.length$

優先度付きキュー#

class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        int n = costs.size();

        // 前 candidates と後 candidates を合計しても costs 配列のサイズを超える場合、
        // costs の最初の k 人の最小コストの労働者の代価のみ必要です
        if (candidates * 2 >= n) {
            sort(costs.begin(), costs.end());
            return accumulate(costs.begin(), costs.begin() + k, 0LL);
        }

        using PII = pair<int, int>;
        auto cmp = [&](const PII &p1, const PII &p2) {
            return p1.first == p2.first ?
                p1.second > p2.second : p1.first > p2.first;
        };
        priority_queue<PII, vector<PII>, decltype(cmp)> heap(cmp);
        // priority_queue<PII, vector<PII>, greater<PII>> heap;

        // 2つの範囲、前 condidates と後 condidates
        // left1, ..., right1, ..., left2, ..., right2
        int left1 = 0, right1 = candidates - 1;
        int left2 = n - candidates, right2 = n - 1;
        for (int i = left1; i <= right1; ++i) {
            heap.push({costs[i], i});
        }
        for (int i = left2; i <= right2; ++i) {
            heap.push({costs[i], i});
        }

        long long res = 0;
        while (k--) {
            auto t = heap.top();
            heap.pop();
            res += t.first;

            // 2つの範囲が重なっている場合
            if (right1 + 1 == left2) {
                continue;
            }

            if (t.second <= right1) {
                ++right1;
                heap.push({costs[right1], right1});
            } else {
                --left2;
                heap.push({costs[left2], left2});
            }
        }
        return res;
    }
};

2462. 雇用K人の労働者の総コスト

2462. 雇佣 K 位工人的总代价#

優先度付きキュー#

2462. 雇佣 K 位工人的总代价 #