数据结构
网络
关系数据库管理系统 (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 次浏览
广告