สมมติว่าเรามีอาร์เรย์ที่เรียกว่าคุณภาพสำหรับคนงานแต่ละคน และมีอาร์เรย์อื่นที่เรียกว่าค่าจ้างและค่า K ผู้ปฏิบัติงานที่ i มีคุณภาพ[i] และค่าจ้างขั้นต่ำที่คาดหวัง[i] เราต้องการจ้างคนงาน K เพื่อจัดตั้งกลุ่มที่ได้รับค่าจ้าง เมื่อเราจ้างคนงานกลุ่ม K เราต้องจ่ายตามกฎต่อไปนี้:
-
ผู้ปฏิบัติงานในกลุ่มที่ได้รับค่าจ้างแต่ละคนควรได้รับค่าจ้างตามอัตราส่วนของคุณภาพโดยเปรียบเทียบกับคนอื่นๆ ในกลุ่มที่ได้รับค่าจ้าง
-
คนงานทุกคนในกลุ่มที่ได้รับค่าจ้างต้องได้รับค่าจ้างอย่างน้อยตามที่คาดหวังไว้
เราต้องหาจำนวนเงินที่น้อยที่สุดที่จำเป็นในการจัดตั้งกลุ่มที่ได้รับค่าตอบแทนตามเงื่อนไขข้างต้น
ดังนั้น หากปัจจัยที่ป้อนเข้ามาเหมือนกับคุณภาพ =[10,22,5] ค่าจ้าง =[70,52,30] และ K =2 ผลลัพธ์จะเป็น 105.000 เพราะเราจะจ่าย 70 ให้กับคนงานคนแรกและ 35 ให้กับคนงาน พนักงานคนที่ 3
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
qr :=รายการใหม่
-
สำหรับแต่ละคู่ (q, w) จากคุณภาพและค่าจ้างทำ
-
แทรก (w/q, q) ต่อท้าย qr
-
-
เรียงลำดับรายการ qr
-
cand :=รายการใหม่ csum :=0
-
สำหรับฉันอยู่ในช่วง 0 ถึง K - 1 ทำ
-
แทรก -qr[i, 1] ลงใน heap cand
-
csum :=csum + qr[i, 1]
-
-
ตอบ :=csum * qr[K - 1, 0]
-
สำหรับ idx ในช่วง K ถึงขนาดของคุณภาพ ให้ทำ
-
แทรก -qr[i, 1] ลงใน heap cand
-
csum :=csum + qr[idx, 1] + องค์ประกอบด้านบนจาก heap cand และลบออกจาก heap
-
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
