徐老师的同桌分配
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
新学期开始啦！少不了的一件事自然就是分配同桌徐老师的班级里有 $n$ 个男生和 $n$ 个女生，男女生坐在一起，正好分成 $n$ 对同桌
而为了促进同学们的学习进步，徐老师决定根据每个同学的成绩情况进行分配同桌
首先徐老师收集了每个同学的平均成绩，第 $i$ 个男生的成绩为 $b_i$，第 i 个女生的成绩为 $g_i$
如果由第 $i$ 个男生和第 $j$ 个女生组成同桌，那么这一对同桌的成绩为 $b_i + g_j$
当分配完 $n$ 对同桌以后，成绩最高的那一对同桌的成绩将代表这一次同桌分配方案的分配度
徐老师认为，分配度越小，这一组分配方案越好，现在徐老师想知道，最小的分配度是多少？
输入格式
第一行一个整数 $n$ 表示男女生人数接下来每行包含两个整数 $b_i$ 和 $g_i$ 分别表示第 $i$ 个男生和第 $i$ 个女生的成绩
对于 $20\%$ 的数据，$1\leq n\leq 5,1\leq a_i,b_i\leq 10$；
对于 $40\%$ 的数据，$1\leq n\leq 100,1\leq a_i,b_i\leq 100$；
对于 $70\%$ 的数据，$1\leq n\leq 10^3,1\leq a_i,b_i\leq 100$；
对于 $100\%$ 的数据，$1\leq n\leq 10^5,1\leq a_i,b_i\leq 100$。
输出格式
输出共 $n$ 行，请计算每新增一对男女生时的最小分配度样例
3
2 8
3 1
1 410
10
9提示
男生 $2$，女生 $8$，分配方案为 $2+8=10$男生 $2,3$，女生 $8,1$，分配方案为 $2+8=10,3+1=4$,分配度为 $max(10,4)=10$
男生 $2,3,1$，女生 $8,1,4$，其中一种分配度最小的方案为 $1+8=9,3+4=7,2+1=3$ 此时分配度是 $max(9,3,7)=9$
23CSP-J秋季普及组模拟赛(2)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 4
- 开始于
- 2023-9-17 12:00
- 结束于
- 2023-9-27 12:00
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 26
