โปรแกรมหาค่าเฉลี่ยอัตราการผ่านสูงสุดใน Python

สมมติว่าเรามีรายชื่อชั้นเรียนที่ class[i] แทน [pass_i, total_i] หมายถึงจำนวนนักเรียนที่สอบผ่านชั้นเรียน ith และจำนวนนักเรียนทั้งหมดของชั้นเรียน ith ตามลำดับ เรายังมีค่าพิเศษอีก สิ่งนี้บ่งชี้ว่ามีนักเรียนเก่งๆ จำนวนมากที่รับประกันว่าจะสอบผ่านในชั้นเรียนใดๆ ที่พวกเขาได้รับมอบหมาย เราต้องมอบหมายนักเรียนพิเศษแต่ละคนเข้าชั้นเรียนในลักษณะที่จะเพิ่มจำนวนนักเรียนโดยเฉลี่ยที่สอบผ่านในทุกชั้นเรียนให้ได้มากที่สุด อัตราส่วนผ่านของชั้นเรียนที่กำหนดโดยจำนวนนักเรียนในชั้นเรียนที่จะผ่านหารด้วยจำนวนนักเรียนทั้งหมดของชั้นเรียน และอัตราส่วนผ่านเฉลี่ยคือผลรวมของอัตราส่วนผ่านของทุกชั้นเรียนหารด้วยจำนวนชั้นเรียน เราต้องหาอัตราการผ่านเฉลี่ยสูงสุดที่เป็นไปได้หลังจากมอบหมายนักเรียนที่เกินมา

ดังนั้น หากอินพุตเหมือนกับคลาส =[[2,3],[4,6],[3,3]] พิเศษ =3 ผลลัพธ์จะเป็น 0.83809 เนื่องจากนักเรียนพิเศษสองคนในชั้นหนึ่งและเพิ่มหนึ่ง นักเรียนพิเศษต่อชั้นสองเพื่อเพิ่มอัตราส่วนให้สูงสุด ตอนนี้ค่าเฉลี่ยคือ (4/5 + 5/7 + 3/3)/3 =0.83809

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• h :=รายการของ tuples เช่น (a/b-(a + 1)/(b + 1), a, b) สำหรับแต่ละคู่ (a, b) ในชั้นเรียน

• heapify h

• ในขณะที่ค่าพิเศษไม่ใช่ศูนย์ให้ทำ

  • (v, a, b) :=ด้านบนของ h และลบออกจาก h

  • (a, b) :=(a + 1, b + 1)

  • แทรก (-(a + 1) /(b + 1) + a / b, a, b) ลงในฮีป

  • พิเศษ :=พิเศษ - 1

• ผลตอบแทนเฉลี่ยจากสิ่งอันดับทั้งหมด 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