g774. 校隊 (School Team) - 高中生程式解題系統

內容

學校組織短跑接力賽校隊，需要從 $N + M$ 個班級裡面選出 $N$ 名男生和 $M$ 名女生。為了使每個班級都有參與感，每班都要派出一人參加，而且由於是校隊，派出的學生必須是該班級同性別中跑百米最快的人。小明身為體育組長，想要選出這 $N$ 男 $M$ 女使得全隊跑百米的總時間越短越好，請幫助他計算出答案。
以下表為例，學校有四個班級，每班的男女生最佳成績如表所示。若需要從四個班級中選出二男二女，則最佳的選法為 1、3 班派女生，2、4 班派男生，時間總和為 $1 + 2 + 2 + 4 = 9$ 。

班級男生最佳成績女生最佳成績
1 3 1

2 2 1

3 4 2

4 4 4

輸入說明

第一行有兩個正整數 $N$ 和 $M$ $(1 \leq N, M \leq 2 \times 10^{3})$ ，分別表示要選出 $N$ 名男生和 $M$ 名女生。接下來 $N + M$ 行每行都有兩個正整數 $B$ 和 $G$ $(1 \leq B, G \leq 10^{4})$ ，分別表示每一班級中男生和女生跑百米的最短時間。同一行的整數間均以空白間隔。

輸出說明

請輸出一個正整數，表示選出 $N$ 名男生和 $M$ 名女生跑百米的最短總時間。

範例輸入 #1

範例輸出 #1

範例輸入 #2

範例輸出 #2

範例輸入 #3

1 1
5 2
2 5

範例輸出 #3

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (5%): 1.0s , <1K
不公開測資點#1 (5%): 1.0s , <1K
不公開測資點#2 (5%): 1.0s , <1K
不公開測資點#3 (5%): 1.0s , <1K
不公開測資點#4 (5%): 1.0s , <1K
不公開測資點#5 (5%): 1.0s , <1K
不公開測資點#6 (5%): 1.0s , <1K
不公開測資點#7 (5%): 1.0s , <1M
不公開測資點#8 (5%): 1.0s , <1M
不公開測資點#9 (5%): 1.0s , <1K
不公開測資點#10 (5%): 1.0s , <1K
不公開測資點#11 (5%): 1.0s , <1M
不公開測資點#12 (5%): 1.0s , <1M
不公開測資點#13 (5%): 1.0s , <1M
不公開測資點#14 (5%): 1.0s , <1M
不公開測資點#15 (5%): 1.0s , <1M
不公開測資點#16 (5%): 1.0s , <1M
不公開測資點#17 (5%): 1.0s , <1M
不公開測資點#18 (5%): 1.0s , <1M
不公開測資點#19 (5%): 1.0s , <1M

提示：

此題目測資分成三組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。
第一組 (30分)： $N, M \leq 10$ 。
第二組 (25分)： $N, M \leq 10^{2}$ 。
第三組 (45分)：沒有特別限制。

標籤:

出處:

TOI 練習賽 202111 潛力組 [管理者： fire5386 (becaidorz) ]

編號	身分	題目	主題	人氣	發表日期
31522	wubaie (小億)	g774	我用 struct + 自訂sort function解	480	2022-08-05 22:05
28384	yes51851823@ ... (wseds)	g774	用DP解卡85%可以參考看看	939	2021-12-06 19:12
28365	r1cky (hehe)	g774	Java 解題心得	979	2021-12-05 12:34