# LeetCode 1792. Maximum Average Pass Ratio

https://leetcode.com/problems/maximum-average-pass-ratio/description/

## 題目大意

已知每班的人數已經通過人數，如何投入神仙學霸 (保證通過) 到各班使平均的通過率最大？

## 思考

野性的直覺告訴你 greedy 就對了

C++ 參考解答：

class Solution
{
public:
    double maxAverageRatio(vector<vector<int>> &classes, int extraStudents)
    {
        priority_queue<ClassRatio> maxHeap;

        for (auto &cl : classes)
        {
            maxHeap.emplace(cl[0], cl[1]);
        }

        while (extraStudents--)
        {
            auto topClass = maxHeap.top();
            maxHeap.pop();
            topClass.addStudent();
            maxHeap.push(topClass);
        }

        double ans = 0;
        while (!maxHeap.empty())
        {
            auto topClass = maxHeap.top();
            maxHeap.pop();
            ans += ratio(topClass.passStdnt, topClass.totalStdnt);
        }

        return ans / classes.size();
    }

private:
    static double ratio(int a, int b) noexcept
    {
        return static_cast<double>(a) / b;
    }

    struct ClassRatio
    {
        int passStdnt;
        int totalStdnt;

        ClassRatio(int pass, int total) noexcept : passStdnt(pass), totalStdnt(total) {}

        double impact() const noexcept
        {
            return ratio(passStdnt + 1, totalStdnt + 1) - ratio(passStdnt, totalStdnt);
        }

        void addStudent() noexcept
        {
            ++passStdnt;
            ++totalStdnt;
        }

        bool operator<(const ClassRatio &other) const noexcept
        {
            return impact() < other.impact();
        }
    };
};

Go 參考解答：

func maxAverageRatio(classes [][]int, extraStudents int) float64 {
	h := &ClassHeap{}
	heap.Init(h)

	for _, c := range classes {
		heap.Push(h, &Class{pass: c[0], total: c[1]})
	}

	for i := 0; i < extraStudents; i++ {
		top := heap.Pop(h).(*Class)
		top.addStudent()
		heap.Push(h, top)
	}

	ans := 0.0
	for h.Len() > 0 {
		top := heap.Pop(h).(*Class)
		ans += top.ratio()
	}

	return ans / float64(len(classes))
}

type Class struct {
	pass, total int
}

func (c *Class) ratio() float64 { return float64(c.pass) / float64(c.total) }

func (c *Class) impact() float64 { return (float64(c.pass+1)/float64(c.total+1) - c.ratio()) }

func (c *Class) addStudent() {
	c.pass++
	c.total++
}

type ClassHeap []*Class

func (h ClassHeap) Len() int           { return len(h) }
func (h ClassHeap) Less(i, j int) bool { return h[i].impact() > h[j].impact() } // Max-heap based on impact.
func (h ClassHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *ClassHeap) Push(x interface{}) { *h = append(*h, x.(*Class)) }

func (h *ClassHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}