สมมติว่าเรามีรายการชั้นเรียนที่ classes[i] แทน [pass_i, total_i] แสดงจำนวนนักเรียนที่สอบผ่านของชั้นเรียนที่ i และจำนวนนักเรียนทั้งหมดของชั้นเรียนที่ i ตามลำดับ เรายังมีอีกค่าหนึ่งคือ extra แสดงจำนวนนักเรียนเก่งเพิ่มเติมที่รับประกันว่าจะสอบผ่านชั้นเรียนใดก็ตามที่ได้รับมอบหมาย เราต้องมอบนักเรียนเพิ่มเติมแต่ละคนให้กับชั้นเรียนอย่างหนึ่งเพื่อให้ได้อัตราส่วนนักเรียนสอบผ่านเฉลี่ยสูงสุดข้ามทุกชั้นเรียน อัตราส่วนการสอบผ่านของชั้นเรียนคำนวณจากจำนวนนักเรียนที่สอบผ่านหารด้วยจำนวนนักเรียนทั้งหมดของชั้นเรียน และอัตราส่วนเฉลี่ยคือผลรวมของอัตราส่วนทุกชั้นเรียนหารด้วยจำนวนชั้นเรียน เราต้องหาอัตราส่วนเฉลี่ยสูงสุดที่เป็นไปได้หลังจากมอบนักเรียนเพิ่มเติม
เช่น ถ้าอินพุตคือ classes = [[2,3],[4,6],[3,3]], extra = 3 ผลลัพธ์จะเป็น 0.83809 เพราะเพิ่มนักเรียนสองคนที่ชั้นเรียนแรกและหนึ่งคนที่ชั้นเรียนที่สองเพื่อเพิ่มอัตราส่วนสูงสุด ดังนั้นค่าเฉลี่ยคือ (4/5 + 5/7 + 3/3)/3 = 0.83809
วิธีแก้ปัญหา
- h := รายการของ tuples เช่น (a/b - (a+1)/(b+1), a, b) สำหรับแต่ละคู่ (a, b) ใน classes
- heapify h
- while extra ไม่เป็นศูนย์:
- (v, a, b) := top ของ h และลบออกจาก h
- (a, b) := (a + 1, b + 1)
- แทรก (-(a+1)/(b+1) + a/b, a, b) ลง heap
- extra := extra - 1
- return ค่าเฉลี่ยจากทุก tuples ของ h
ตัวอย่าง
import heapq
def solve(classes, extra):
h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]
heapq.heapify(h)
while extra:
v, a, b = heapq.heappop(h)
a, b = a + 1, b + 1
heapq.heappush(h, (-(a + 1) / (b + 1) + a / b, a, b))
extra -= 1
return sum(a / b for v, a, b in h) / len(h)
classes = [[2,3],[4,6],[3,3]]
extra = 3
print(solve(classes, extra))
อินพุต
[[2,3],[4,6],[3,3]], 3
เอาต์พุต
0
