题目详情
返回题库题目描述
新学期开始啦！少不了的一件事自然就是分配同桌
徐老师的班级里有n个男生和n个女生，男女生坐在一起，正好分成n对同桌
而为了促进同学们的学习进步，徐老师决定根据每个同学的成绩情况进行分配同桌
首先徐老师收集了每个同学的平均成绩，第 i个男生的成绩为 bi，第i个女生的成绩为gi
如果由第 i个男生和第 j个女生组成同桌，那么这一对同桌的成绩为bi+gj
当分配完n对同桌以后，成绩最高的那一对同桌的成绩将代表这一次同桌分配方案的分配度
徐老师认为，分配度越小，这一组分配方案越好，现在徐老师想知道，最小的分配度是多少？
输入描述
第一行一个整数n表示男女生人数
接下来每行包含两个整数bi 和 gi分别表示第 i个男生和第 i个女生的成绩
对于20%的数据，1<=n<=5,1<=bi,gi<=10；
对于40%的数据，1<=n<=100,1<=bi,gi<=100；
对于70%的数据，1<=n<=1000,1<=bi,gi<=100；
对于100%的数据，1<=n<=100000,1<=bi,gi<=100；
输出描述
输出共 n行，请计算每新增一对男女生时的最小分配度
提示
男生 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,7,3)=9