算法01——patA1080 研究生入学

本文主要是介绍算法01——patA1080 研究生入学，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题意：

   有N位考生，M所学校，每位考生都有K个志愿学校，每个学校也有招生人数限制。现在给出所有考生的初试成绩GE，面试成绩GI以及K个志愿学校的编号，要求模拟学校录取招生的过程，并给出每个学校录取的考生编号(按从小到大排序)。下面是录取规则：

• 先按考生的总分(GE+GI)/2从高到低排序，总分相同的按照GE从高到低排序。如果仍然相同，则按相同排名处理
• 按排名先后顺序考虑每个考生最终录取的学校。对每个考生，按K个志愿先后顺序考虑：如果当前志愿学校的已招生人数未到达该校的招生人数总额度，那么该学校录取此同学，并且不考虑该同学后面的志愿；如果当前志愿学校的已招生人数达到招生人数的总额度，且该校上一个录取考生的排名与此学生的排名相同，则可不受招生人数的限制，由该学校破格录取他。除了上面两种情况，均视为该志愿学校无法录取该考生，转而考虑该考生的下一个志愿学校。如果该考生的所有志愿学校都无法录取该考生，那么该考生落榜。

输入格式：
  第一行输入三个整数：N(<=40000)总的考生数量；M(<=100)志愿学校数量；K(<=5)每个考生的志愿学校数目。第二行是M个整数，为每个志愿学校的招生总额度。接下来的N行，每行有2+K个整数，前两个整数分别是每个考生的GE和GI成绩，然后K个整数为考生的志愿学校。假定学校编号为0 ~ M-1，考生编号为0 ~ N-1

输出格式：

  按照学校编号从小到大，逐行输出每个学校录取的学生编号，学生编号也从小到大排列。如果一个学校没有录取任何学生，则此行为空行。

输入样例：

11 6 3
2 1 2 2 2 3
100 100 0 1 2
60 60 2 3 5
100 90 0 3 4
90 100 1 2 0
90 90 5 1 3
80 90 1 0 2
80 80 0 1 2
80 80 0 1 2
80 70 1 3 2
70 80 1 2 3
100 100 0 2 4

输出样例：

0 10
3 
5 6 7
2 8

1 4

思路：

1. 根据题中设计的信息，需要设计结构体类型Student用于存放考生的初试成绩GE、面试成绩GI、成绩总和sum(即GI+GE,不必除以2)、排名r、考生编号stuID以及K个志愿学校的编号。此外，还要定义结构体类型School用于存放该学校的招生总额度quota、当前实际招生人数stuSum、招收的考生编号数组id[]以及学校当前最后一个招收的考生编号lastAdmit
2. 要对所有考生按照题目要求进行排序
3. 对于考生的每个志愿，如果当前志愿学校的考生人数未达到总额或者该校上一个录取考生的排名与该考生排名相同，那么可以录取该生
4. 对每个学校，录取的考生按照ID从小到大排序，并按学校的顺序进行输出

代码：

#include<cstdio>
#include<algorithm>
using namespace std;

struct Student {
    int GE,GI,sum;
    int r,stuID;
    int cho[6];//志愿学校编号
}stu[40010];

struct School {
    int quota;
    int stuSum;//目前实际招生人数
    int id[40010];//已录取的考生编号
    int lastAdmit;//上一个招收的学生编号
}sch[110];

bool cmp(Student stu1 , Student stu2){
    if(stu1.sum != stu2.sum)
        return stu1.sum > stu2.sum;
    else
        return stu1.GE > stu2.GE;
}

bool cmpID(int a , int b){
    return stu[a].stuID < stu[b].stuID;
}

int main(){
    int n,m,k;
    scanf("%d %d %d",&n,&m,&k);
    for(int i = 0 ; i < m ; i++){
        scanf("%d",&sch[i].quota);
        sch[i].stuSum = 0 ;
        sch[i].lastAdmit = -1;//最后一个招生的学生编号为-1表示不存在
    }
    for(int i = 0 ; i < n ; i++){
        stu[i].stuID = i ;
        scanf("%d %d",&stu[i].GE,&stu[i].GI);
        stu[i].sum = stu[i].GE+stu[i].GI;
        for(int j = 0 ; j < k ; j++ ){
            scanf("%d",&stu[i].cho[j]);
        }
    }
    sort(stu,stu+n,cmp);
    for(int i = 0 ; i < n ; i++){//计算考生排名
        if(i>0&&stu[i].sum == stu[i-1].sum&&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].cho[j];//考生志愿
            int num = sch[choice].stuSum;
            int last = sch[choice].lastAdmit;
            if(num < sch[choice].quota || (last!=-1&&stu[i].r==stu[last].r)){
                sch[choice].id[num] = i;
                sch[choice].lastAdmit = i;
                sch[choice].stuSum++;
                break;
            }
        }
    }
    for(int i = 0 ; i < m ; i++){
        if(sch[i].stuSum > 0){
            //如果有招收到学生
            sort(sch[i].id,sch[i].id+sch[i].stuSum,cmpID);
            for(int j = 0 ; j < sch[i].stuSum ; j++){
                printf("%d",stu[sch[i].id[j]].stuID);
                if(j < sch[i].stuSum - 1)
                    printf(" ");
            }
        }
        printf("\n");
    }
    return 0;
}

这篇关于算法01——patA1080 研究生入学的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！