각 작업자에 대해 quality라는 배열이 있고 임금이라는 또 다른 배열이 있고 값 K가 있다고 가정합니다. i 번째 작업자는 품질[i]과 최저 임금 기대 임금[i]을 가지고 있습니다. 유료 그룹을 구성할 K명의 직원을 고용하고 싶습니다. K 직원 그룹을 고용할 때 다음 규칙에 따라 급여를 지급해야 합니다.
-
유급 그룹의 각 근로자는 유급 그룹의 다른 직원과 비교하여 품질의 비율로 급여를 받아야 합니다.
-
유급 그룹의 모든 근로자는 최소 기대 임금 이상을 받아야 합니다.
위의 조건을 만족하는 유료 그룹을 구성하는 데 필요한 최소 금액을 찾아야 합니다.
따라서 입력이 품질 =[10,22,5], 임금 =[70,52,30] 및 K =2와 같으면 첫 번째 작업자에게 70을 지불하고 작업자에게 35를 지불하므로 생산량은 105.000이 됩니다. 세 번째 작업자입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
qr :=새 목록
-
품질과 임금에서 각 쌍(q, w)에 대해 수행
-
qr 끝에 (w/q, q) 삽입
-
-
목록 정렬 qr
-
cand :=새 목록, csum :=0
-
범위 0에서 K - 1에 있는 i에 대해 수행
-
-qr[i, 1]을 힙 캔드에 삽입
-
csum :=csum + qr[i, 1]
-
-
ans :=csum * qr[K - 1, 0]
-
범위 K에서 품질 크기까지의 idx에 대해
-
-qr[i, 1]을 힙 캔드에 삽입
-
csum :=csum + qr[idx, 1] + 힙 cand의 최상위 요소 및 힙에서 삭제
-
ans =ans의 최소값 및 (csum * qr[idx][0])
-
-
반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다.
import heapq
def solve(quality, wage, K):
qr = []
for q, w in zip(quality, wage):
qr.append([w/q, q])
qr.sort()
cand, csum = [], 0
for i in range(K):
heapq.heappush(cand, -qr[i][1])
csum += qr[i][1]
ans = csum * qr[K - 1][0]
for idx in range(K, len(quality)):
heapq.heappush(cand, -qr[idx][1])
csum += qr[idx][1] + heapq.heappop(cand)
ans = min(ans, csum * qr[idx][0])
return ans
quality = [10,22,5]
wage = [70,52,30]
K = 2
print(solve(quality, wage, K)) 입력
[10,22,5], [70,52,30], 2
출력
105