성능과 비용이라는 길이가 같은 두 개의 숫자 목록이 있다고 가정합니다. 그리고 또 다른 숫자 k가 있습니다. 이는 각 작업자 i가 성능[i] 수준에서 수행하고 비용이 최소한 비용[i]임을 나타냅니다. 직원들이 그룹의 다른 직원에 비해 성과에 비례하여 급여를 받을 것이라는 점을 감안할 때 k 직원을 고용하기 위한 최소 비용을 찾아야 합니다.
따라서 입력이 performance =[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 정의
-
initialize i :=0의 경우, i
-
idx :=seq[i]
-
pq에 p[idx] 삽입
-
psum :=psum + p[idx]
-
크기가 pq> k인 경우 -
-
psum :=psum - pq의 최상위 요소
-
pq에서 최상위 요소 삭제
-
-
i>=k − 1이면 −
-
ans :=ans의 최소값 및 (c[idx] / p[idx] * psum)
-
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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