資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：根據員工績效計算最終應付金額
假設我們有兩個相同長度的數字列表，分別稱為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的值填充seq
根據以下條件對陣列seq進行排序：(c[i] * p[j] < c[j] * p[i])
ans := inf, psum := 0
定義一個優先佇列pq
初始化i := 0，當i < n時，更新（i加1），執行：
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
更新於：2020-12-26
168 次瀏覽
廣告