标题1005:Graduate Admission
题目1005:Graduate Admission
题目1005:Graduate Admission
/********************************* * 日期:2013-2-27 * 作者:SJF0115 * 题号: 九度OJ 题目1005:Graduate Admission * 来源:http://ac.jobdu.com/problem.php?pid=1005 * 结果:AC * 来源:2011年浙江大学计算机及软件工程研究生机试真题 * 总结: **********************************/ #include <stdio.h> #include <stdlib.h> //结构体 typedef struct Application{ int GI;//复试成绩 int GE;//初试成绩 int GF;//总成绩 int PS[6];//偏爱的学校 int ID;//编号 }Application; typedef struct School{ int Quota;//学校名额 int count;//实际招收人数 int AppID[4001];//招收人的ID }School; Application app[40001]; School school[101]; //排序函数 int cmp(const void *a, const void *b){ struct Application *c = (Application *)a; struct Application *d = (Application *)b; if(c->GF != d->GF){ return d->GF - c->GF; } else if(c->GE != d->GE){ return d->GE - c->GE; } } int cmp2(const void *a,const void *b){ return *(int *)a - *(int *)b; } int main () { //N the total number of applicants; //M the total number of graduate schools //K the number of choices an applicant may have. int N,M,K,i,j,SID; while(scanf("%d %d %d",&N,&M,&K) != EOF){ //每个学校的名额 for(i = 0;i < M;i++){ scanf("%d",&school[i].Quota); school[i].count = 0; } for(i = 0;i < N;i++){ //初试成绩 复试成绩 scanf("%d %d",&app[i].GE,&app[i].GI); //总成绩 app[i].GF = (app[i].GE + app[i].GI) / 2; //偏爱的学校 for(j = 0;j < K;j++){ scanf("%d",&app[i].PS[j]); } app[i].ID = i; }//for //排序 qsort(app,N,sizeof(app[0]),cmp); //安排招生 for(i = 0;i < N;i++){ for(j = 0;j < K;j++){ SID = app[i].PS[j]; //如果SID学校还没有招满 if(school[SID].Quota > 0){ school[SID].AppID[school[SID].count] = i; school[SID].count ++; school[SID].Quota --; break; } //已经招满 else{ //最后一个招生人的ID int index = school[SID].AppID[school[SID].count - 1]; //如果所有成绩都一样,即使学校已经招满一样被录取 if(app[i].GF == app[index].GF && app[i].GE == app[index].GE){ school[SID].AppID[school[SID].count] = i; school[SID].count ++; school[SID].Quota --; break; } } }//for }//for for(i = 0;i < M;i++){ for(j = 0;j < school[i].count;j++){ school[i].AppID[j] = app[school[i].AppID[j]].ID; } } //输出学校招收情况 for(i = 0;i < M;i++){ //该学校没有招收到学生 if(school[i].count == 0){ printf("\n"); } //该学校招收到1名学生 else if(school[i].count == 1){ printf("%d\n",school[i].AppID[0]); } //该学校招收到大于1名学生,需排序安编号大小输出 else{ //排序输出 qsort(school[i].AppID,school[i].count,sizeof(int),cmp2); int first = 1; for(j = 0;j < school[i].count;j++){ if(first){ first = 0; } else{ printf(" "); } printf("%d",school[i].AppID[j]); } printf("\n"); } }//for }//while return 0; }
注意:
考虑到边界条件比如
11 6 3
0 0 0 2 2 3
100 100 0 1 2
100 100 0 1 2
100 100 0 1 2
100 100 0 1 2
100 100 0 1 2
100 100 0 1 2
100 100 0 1 2
100 100 0 1 2
100 100 0 1 2
100 100 0 1 2
100 100 0 1 2
学校0,1,2招生人数都为零,11个学生没一个能录取。