#28365: Java 解題心得


r1cky (tour1st)

School : No School
ID : 158637
IP address : [1.34.88.173]
Last Login :
2022-09-25 19:52:01
g774. 校隊 (School Team) -- TOI練習賽202111潛力組 | From: [114.32.128.128] | Post Date : 2021-12-05 12:34

這題我用DP解(有人跟我說可以Greedy,但不知道真的假的,如果有人知道可以回復我)

參考解法:https://r1cky.pixnet.net/blog/post/53032771

 
#28378: Re:Java 解題心得


wallacechu0409@gmail.com (Wallace Chu)

School : 國立臺灣師範大學附屬高級中學
ID : 136430
IP address : [58.114.186.98]
Last Login :
2022-09-10 19:28:50
g774. 校隊 (School Team) -- TOI練習賽202111潛力組 | From: [119.14.208.15] | Post Date : 2021-12-05 22:47

這題我用DP解(有人跟我說可以Greedy,但不知道真的假的,如果有人知道可以回復我)

參考解法:https://r1cky.pixnet.net/blog/post/53032771


我是請教電神,也是用dp

 
#28381: Re:Java 解題心得


fire5386 (Penguin07)

School : 國立清華大學
ID : 115822
IP address : [140.114.218.50]
Last Login :
2022-09-26 20:23:52
g774. 校隊 (School Team) -- TOI練習賽202111潛力組 | From: [180.217.9.10] | Post Date : 2021-12-06 17:14

確實有人用greedy 計算每個班級的差(男-女)然後排序 最大的n個取男生 剩下取女生

 
#28386: Re:Java 解題心得


linlincaleb@gmail.com (臨末之頌)

School : 新北市立板橋高級中學
ID : 132772
IP address : [203.64.161.143]
Last Login :
2022-09-22 09:19:31
g774. 校隊 (School Team) -- TOI練習賽202111潛力組 | From: [111.248.141.16] | Post Date : 2021-12-06 19:50

確實有人用greedy 計算每個班級的差(男-女)然後排序 最大的n個取男生 剩下取女生

greedy直觀又好用,複雜度又小,超讚

 
#28400: Re:Java 解題心得


r1cky (tour1st)

School : No School
ID : 158637
IP address : [1.34.88.173]
Last Login :
2022-09-25 19:52:01
g774. 校隊 (School Team) -- TOI練習賽202111潛力組 | From: [114.32.128.128] | Post Date : 2021-12-07 19:13

確實有人用greedy 計算每個班級的差(男-女)然後排序 最大的n個取男生 剩下取女生


感謝。這樣似乎greedy的解法比較簡潔,而且複雜度還比較小

DP O(mn) v.s.

Greedy O(tlogt)(假設總人數t=m+n)

 
ZeroJudge Forum