Giả sử có danh sách các lớp classes[i] = [pass_i, total_i] là số học sinh đỗ và tổng học sinh lớp i. Có thêm extra học sinh giỏi chắc chắn đỗ. Phân bổ extra học sinh vào các lớp để tối đa hóa tỷ lệ đỗ trung bình. Tỷ lệ đỗ lớp = pass/total. Trung bình = tổng tỷ lệ / số lớp.
Ví dụ: classes = [[2,3],[4,6],[3,3]], extra = 3, đầu ra = 0.83809 (phân bổ 2 cho lớp 1, 1 cho lớp 2).
Giải pháp
Sử dụng max-heap (priority queue) chọn lớp tăng tỷ lệ đỗ nhiều nhất khi thêm 1 học sinh:
- h := danh sách tuple (a/b - (a+1)/(b+1), a, b) cho mỗi (a,b) trong classes
- heapify h (max-heap bằng cách lấy âm giá trị tăng)
- Khi extra > 0:
- Pop (v, a, b) từ h
- a, b := a+1, b+1
- Push (-(a+1)/(b+1) + a/b, a, b) vào heap
- extra -= 1
- Trả về trung bình a/b từ tất cả tuple trong h
Ví dụ minh họa
Xem 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.8380952380952381