2023-06-22：一所學(xué)校里有一些班級(jí)，每個(gè)班級(jí)里有一些學(xué)生，現(xiàn)在每個(gè)班都會(huì)進(jìn)行一場(chǎng)期
2023-06-22：一所學(xué)校里有一些班級(jí)，每個(gè)班級(jí)里有一些學(xué)生，現(xiàn)在每個(gè)班都會(huì)進(jìn)行一場(chǎng)期末考試
給你一個(gè)二維數(shù)組 classes ，其中 classes[i] = [passi, totali]
表示你提前知道了第 i 個(gè)班級(jí)總共有 totali 個(gè)學(xué)生，其中只有 passi 個(gè)學(xué)生可以通過(guò)考試
給你一個(gè)整數(shù) extraStudents ，表示額外有 extraStudents 個(gè)聰明的學(xué)生
他們 一定 能通過(guò)任何班級(jí)的期末考
你需要給這 extraStudents 個(gè)學(xué)生每人都安排一個(gè)班級(jí)
使得 所有 班級(jí)的 平均 通過(guò)率 最大 。
一個(gè)班級(jí)的 通過(guò)率 等于這個(gè)班級(jí)通過(guò)考試的學(xué)生人數(shù)除以這個(gè)班級(jí)的總?cè)藬?shù)
平均通過(guò)率 是所有班級(jí)的通過(guò)率之和除以班級(jí)數(shù)目。
請(qǐng)你返回在安排這 extraStudents 個(gè)學(xué)生去對(duì)應(yīng)班級(jí)后的 最大 平均通過(guò)率
與標(biāo)準(zhǔn)答案誤差范圍在 10^-5 以內(nèi)的結(jié)果都會(huì)視為正確結(jié)果。
輸入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2。
輸出：0.78333。
答案2023-06-22：
大體步驟如下：
1.定義一個(gè)結(jié)構(gòu)體?Party?來(lái)表示班級(jí)的通過(guò)情況，結(jié)構(gòu)體包含兩個(gè)浮點(diǎn)數(shù)字段，表示通過(guò)考試的學(xué)生人數(shù)和班級(jí)的總?cè)藬?shù)。
2.實(shí)現(xiàn)?Party?結(jié)構(gòu)體的方法?benefit()，計(jì)算班級(jí)的收益，即通過(guò)率的增益。
3.定義一個(gè)類型為?PartyHeap?的堆，用于按照班級(jí)的收益對(duì)班級(jí)進(jìn)行排序。
4.實(shí)現(xiàn)?PartyHeap?的方法?Len()、Less()、Swap()，用于定義堆的行為。
5.實(shí)現(xiàn)?PartyHeap?的方法?Push()?和?Pop()，用于向堆中添加和移除元素。
6.定義一個(gè)函數(shù)?maxAverageRatio(classes [][]int, extraStudents int) float64，接收班級(jí)信息和額外學(xué)生數(shù)量。
7.創(chuàng)建一個(gè)空的?PartyHeap?堆。
8.遍歷班級(jí)信息，將每個(gè)班級(jí)的通過(guò)情況添加到堆中。
9.使用循環(huán)將額外的學(xué)生分配到班級(jí)中。
10.循環(huán)堆中的班級(jí)，計(jì)算平均通過(guò)率，累加通過(guò)率到變量?all?中。
11.返回平均通過(guò)率?all?除以班級(jí)數(shù)量的浮點(diǎn)數(shù)。
時(shí)間復(fù)雜度：
??初始化堆：O(nlogn)，其中 n 是班級(jí)的數(shù)量。初始化堆的時(shí)間復(fù)雜度是 O(nlogn)。
??添加額外學(xué)生到班級(jí)：O(klogn)，其中 k 是額外學(xué)生的數(shù)量，n 是班級(jí)的數(shù)量。每次添加一個(gè)學(xué)生需要進(jìn)行一次堆操作，堆操作的時(shí)間復(fù)雜度是 O(logn)，因此添加額外學(xué)生的總時(shí)間復(fù)雜度是 O(klogn)。
??計(jì)算平均通過(guò)率：O(nlogn)，其中 n 是班級(jí)的數(shù)量。循環(huán)遍歷堆中的班級(jí)，每次從堆中彈出一個(gè)班級(jí)，堆操作的時(shí)間復(fù)雜度是 O(logn)，總體時(shí)間復(fù)雜度為 O(nlogn)。
綜上所述，整個(gè)算法的時(shí)間復(fù)雜度是 O(nlogn + klogn)。
空間復(fù)雜度：
??除了輸入的班級(jí)和學(xué)生信息外，算法使用了一個(gè)堆來(lái)存儲(chǔ)班級(jí)信息，堆的空間復(fù)雜度是 O(n)。
??其他變量和臨時(shí)存儲(chǔ)空間的空間復(fù)雜度可以忽略不計(jì)。
因此，整個(gè)算法的空間復(fù)雜度是 O(n)。
go完整代碼如下：
package?main
import?(
????"container/heap"
????"fmt"
)
type?Party?struct?{
????pass??float64
????total?float64
}
func?(p?Party)?benefit()?float64?{
????return?(p.pass+1)/(p.total+1)?-?(p.pass?/?p.total)
}
type?PartyHeap?[]Party
func?(h?PartyHeap)?Len()?int???????????{?return?len(h)?}
func?(h?PartyHeap)?Less(i,?j?int)?bool?{?return?h[i].benefit()?>?h[j].benefit()?}
func?(h?PartyHeap)?Swap(i,?j?int)??????{?h[i],?h[j]?=?h[j],?h[i]?}
func?(h?*PartyHeap)?Push(x?interface{})?{
????*h?=?append(*h,?x.(Party))
}
func?(h?*PartyHeap)?Pop()?interface{}?{
????old?:=?*h
????n?:=?len(old)
????x?:=?old[n-1]
????*h?=?old[:n-1]
????return?x
}
func?maxAverageRatio(classes?[][]int,?extraStudents?int)?float64?{
????h?:=?&PartyHeap{}
????heap.Init(h)
????for?_,?p?:=?range?classes?{
????????heap.Push(h,?Party{pass:?float64(p[0]),?total:?float64(p[1])})
????}
????for?i?:=?0;?i?<?extraStudents;?i++?{
????????cur?:=?heap.Pop(h).(Party)
????????cur.pass++
????????cur.total++
????????heap.Push(h,?cur)
????}
????var?all?float64
????for?h.Len()?>?0?{
????????cur?:=?heap.Pop(h).(Party)
????????all?+=?cur.pass?/?cur.total
????}
????return?all?/?float64(len(classes))
}
func?main()?{
????classes?:=?[][]int{{1,?2},?{3,?5},?{2,?2}}
????extraStudents?:=?2
????result?:=?maxAverageRatio(classes,?extraStudents)
????fmt.Printf("Result:?%f\n",?result)
}
c++完整代碼如下：
struct?Party?{
????double?pass;
????double?total;
????double?benefit()?const?{
????????return?(pass?+?1)?/?(total?+?1)?-?(pass?/?total);
????}
};
struct?PartyCompare?{
????bool?operator()(const?Party&?p1,?const?Party&?p2)?const?{
????????return?p1.benefit()?<?p2.benefit();
????}
};
double?maxAverageRatio(std::vector<std::vector<int>>&?classes,?int?extraStudents)?{
????std::priority_queue<Party,?std::vector<Party>,?PartyCompare>?heap;
????for?(const?auto&?p?:?classes)?{
????????heap.push({?static_cast<double>(p[0]),?static_cast<double>(p[1])?});
????}
????for?(int?i?=?0;?i?<?extraStudents;?i++)?{
????????Party?cur?=?heap.top();
????????heap.pop();
????????cur.pass?+=?1;
????????cur.total?+=?1;
????????heap.push(cur);
????}
????double?all?=?0;
????while?(!heap.empty())?{
????????Party?cur?=?heap.top();
????????heap.pop();
????????all?+=?cur.pass?/?cur.total;
????}
????return?all?/?classes.size();
}
int?main()?{
????std::vector<std::vector<int>>?classes?=?{?{1,?2},?{3,?5},?{2,?2}?};
????int?extraStudents?=?2;
????double?result?=?maxAverageRatio(classes,?extraStudents);
????std::cout?<<?"Result:?"?<<?result?<<?std::endl;
????return?0;
}
