前言

传送门

正文

参考题解

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

/* 模拟研究生院录取学生 题意： 输入n,m,k，分别表示n个申请者，m所高校和每个申请者可以填报的k个志愿 接下来一行输入m所高校各自的招生名额，随后n行，每行输入2+k个整数，前两个数 分别表示grade_e(初试成绩)、grade_i(复试成绩)，k个志愿。高校从0~m-1编号、申请者 从0~n-1编号。 录取规则： 1、申请者按照他们的总成绩（即初试成绩和复试成绩的平均值） 排名，如果总成绩相同，则按照初试成绩排名， 若初试成绩也相同，则他们的排名相同。 2、每个申请者有k个志愿可以填报，按照从第一志愿依次进行录取 ，若果某个志愿高校招生名额没满，则可以录取该申请者 若果该申请者所有的志愿高校都拒绝了他，则最终不需输出 3、注意如果申请者的排名相同，且同时填报了同一所高校，那么高校必须同时录取这些排名相同的志愿者，即使高校的 招生名额已经满了。（即高校录取的最后一名学生的排名与当前申请者排名相同，那么该申请者可以被破格录取） 注意点： 1、 最后输出的时候，是需要输出学生原先的编号，而sch中的ids数组保存的是学生排完序后的下标，并不是原先读入时的编号 2、 注意学生的编号排序 */
const int N=4e4+10;
int n,m,k;
struct Student{
	int r,sId;//排名，用户编号（下标） 
	int GE,GI,total;//初试成绩、复试成绩以及总成绩 
	int choices[6]; //志愿列表 
}stu[N]; 

struct School{
	int quota;//招生名额
	int realNum;//实际招生人数
	int ids[N];//招生的学生编号
	int lastId;//当前录取的最后一名学生的编号 
}sch[110];

//学生名次排序 
bool cmpStu(Student a,Student b){
	if(a.total!=b.total)return a.total>b.total;
	else return a.GE>b.GE;
}

//学校录取学生的编号排序
bool cmpId(int a,int b){
	return stu[a].sId<stu[b].sId; 
} 
int main(){
	scanf("%d %d %d",&n,&m,&k);
	for(int i=0;i<m;i++){
		scanf("%d",&sch[i].quota);
		sch[i].realNum=0;
		sch[i].lastId=-1;//-1表示当前还未招生 
	}
	
	for(int i=0;i<n;i++){
		scanf("%d %d",&stu[i].GE,&stu[i].GI);
		stu[i].sId=i; 
		stu[i].total=stu[i].GE+stu[i].GI;
		for(int j=0;j<k;j++){
			scanf("%d",&stu[i].choices[j]);
		}
	} 
	
	sort(stu,stu+n,cmpStu);
// 计算每一位考生的排名
	for(int i=0;i<n;i++){
// 与前一名的总分相同且初试成绩相同，则排名相同 
		if(i>0&&stu[i].total==stu[i-1].total&&stu[i].GE==stu[i-1].GE){
			stu[i].r=stu[i-1].r;
		}else{
			stu[i].r=i;
		}
	} 
	
// 判断每位学生被哪所学校录取 
	for(int i=0;i<n;i++){
		for(int j=0;j<k;j++){
			int choice=stu[i].choices[j];//当前志愿的学校编号 
			int realNum=sch[choice].realNum;//当前学校的实际招生人数
			int lastId=sch[choice].lastId;//当前学校录取的最后一名学生的编号
			if(realNum<sch[choice].quota||(lastId!=-1&&stu[i].r==stu[lastId].r)){//正常录取或者破格录取 
				sch[choice].ids[realNum]=i;//录取该学生 
				sch[choice].lastId=i;//更新录取的最后一名学生的编号 
				sch[choice].realNum++;//更新实际录取的人数 
				break; 
			}
		}
	} 
	
	for(int i=0;i<m;i++){
		if(sch[i].realNum>0){//学校招生人数不为0 
			sort(sch[i].ids,sch[i].ids+sch[i].realNum,cmpId);//对录取的学生进行排序
			for(int j=0;j<sch[i].realNum;j++){
// 这里需要注意，由于对stu进行了排序，因此学生的顺序被打乱了，而输出要求输出原先的编号，而不是排序
// 后的下标，因此是stu[sch[i].ids[j]].sId 
				if(j==0)printf("%d",stu[sch[i].ids[j]].sId);
				else printf(" %d",stu[sch[i].ids[j]].sId);
			} 
			printf("\n");
		}else printf("\n");
	} 
	
	return 0;
}