Giả sử chúng ta có một danh sách các lớp trong đó các lớp [i] đại diện cho [pass_i, total_i] đại diện cho số học sinh đã vượt qua kỳ kiểm tra của lớp thứ i và tổng số học sinh của lớp thứ i tương ứng. Chúng tôi cũng có một giá trị bổ sung. Điều này cho thấy có thêm số lượng học sinh xuất sắc được đảm bảo sẽ vượt qua kỳ thi của bất kỳ lớp nào mà họ được chỉ định. Chúng ta phải chỉ định mỗi học sinh thêm vào một lớp sao cho tối đa hóa số học sinh đạt trung bình trên tất cả các lớp. Tỷ lệ đậu của một lớp được xác định bằng số học sinh của lớp sẽ đậu chia cho tổng số học sinh của lớp. Và tỷ lệ đỗ trung bình là tổng tỷ lệ đỗ của tất cả các lớp chia cho số lớp. Chúng tôi phải tìm tỷ lệ đậu trung bình tối đa có thể sau khi chỉ định các học sinh bổ sung.
Vì vậy, nếu đầu vào giống như các lớp =[[2,3], [4,6], [3,3]], extra =3, thì đầu ra sẽ là 0,83809, bởi vì hai học sinh thêm ở lớp đầu tiên và thêm một học sinh thêm vào lớp hai để tỉ số lớn nhất nên trung bình bây giờ là (4/5 + 5/7 + 3/3) / 3 =0,83809.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
h:=danh sách các bộ giá trị như (a / b- (a + 1) / (b + 1), a, b) cho mỗi cặp (a, b) trong các lớp
-
đống h
-
trong khi phần phụ là khác 0, thực hiện
-
(v, a, b):=top of h, và xóa nó khỏi h
-
(a, b):=(a + 1, b + 1)
-
chèn (- (a + 1) / (b + 1) + a / b, a, b) vào heap
-
thêm:=thêm - 1
-
-
trung bình trở lại từ tất cả các bộ giá trị của h
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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)) Đầu vào
[[2,3],[4,6],[3,3]], 3
Đầu ra
0