C++でK人の労働者を雇うための最小コスト

N人の労働者がいると仮定します。各ワーカーには品質パラメーターがあります。 i番目の労働者は質[i]と最低賃金期待賃金[i]を持っています。今度はK人の労働者を雇って有給のグループを作りたいと思います。 K人の労働者のグループを雇用する場合、次の規則に従って彼らに支払う必要があります-

• 有給グループの各労働者は、有給グループの他の労働者と比較することにより、質の比率で支払われるべきです。

• 有給グループのすべての労働者は、少なくとも最低賃金の期待を支払わなければなりません。

上記の条件を満たす有料グループを形成するために必要な最小限の金額を見つける必要があります。

したがって、入力が品質=[10,22,5]、賃金=[70,52,30]、K =2のような場合、出力は105.000になります。これは、最初の労働者に70、3番目の労働者に35を支払うためです。

これを解決するには、次の手順に従います-

• q、w、rでデータを定義する

• n：=品質のサイズ

• サイズnのデータvの配列を作成します

• 初期化i：=0の場合、i

  • q of v [i]：=quality [i]

  • v [i]のw：=賃金[i]

  • r of v [i]：=w of v [i] / q of v [i]

• r値に基づいて配列vを並べ替えます

• temp：=0

• 合計：=0

• ans：=inf

• 1つの優先キューpqを定義する

• 初期化i：=0の場合、i

  • pqのサイズがkと同じ場合、-

    • x：=pqの最上位要素

    • 合計：=合計-x

    • pqから要素を削除する

  • pqのサイズがk-1と同じ場合、-

    • ans：=最小（v[i]の合計*r）+v[i]とansのw

  • sum：=sum + q of v [i]

  • v[i]のqをpqに挿入します

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

#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 temp = 0;
      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