C++でのパフォーマンスに基づいて従業員に支払われるべき最終的な金額を見つけるためのプログラム

したがって、入力がパフォーマンス=[5、3、2]コスト=[100、5、4] k =2のような場合、emp1とemp2を選択できるため、出力は10になります。少なくとも5+4=9の金額を支払う必要があります。ただし、emp1のパフォーマンスはemp2の1.5倍であるため、少なくとも1.5 * 4 =6を支払う必要があります。したがって、合計で6 + 4=10になります。

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

• n：=cのサイズ

• サイズnの配列シーケンスを定義します

• seqに0からn-1までの値を入力します

• これらの基準に基づいて配列seqをソートします（c [i] * p [j]

• ans：=inf、psum：=0

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

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

  • idx：=seq [i]

  • p[idx]をpqに挿入します

  • psum：=psum + p [idx]

  • pq> kのサイズの場合、-

    • psum：=psum −pqの最上位要素

    • pqから最上位の要素を削除します

  • i> =k − 1の場合、−

    • ans：=ansの最小値と（c [idx] / p [idx] * psum）

• ansを返す

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

例

#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