[sort自定义排序,结构体及for循环枚举]录取通知书

录取通知书

题目描述

2024年高考结束了，几位同学兴奋地等待着录取结果，你恰好知道各高校录取计划、所有考生的高考成绩和志愿填报，请你提前告诉这几名同学他们分别会收到哪所高校的录取吧。
假设高考排名规则如下:按照总分由高到低排序，如果总分相同，数学成绩高的排名靠前，如果数学排名仍相同，理综成绩高的靠前，如果理综排名仍相同，语文成绩高的靠前。
录取规则如下:由考生排名由高到低依次录取，每名考生可以填写0~3个志愿，考生会录取到尚有名额的志愿排序最前的院校，如果所有志愿的院校都已经没有名额，那这名考生不会被任何院校录取。

关于输入

第一行包含三个整数N、M、K，分别表示学校的数量、学生的数量和查询的学生数量。
接下来的N行，每行包含两个整数，表示学校的ID和招生名额。
接下来的M行，每行包含九个整数，表示学生的ID、总分、数学成绩、理综成绩、语文成绩、英语成绩以及三个志愿学校的选择（-1表示放弃该志愿及后续所有志愿填报）。
最后一行包含K个整数，表示待查询学生的ID。
测试数据的限制如下:
学校的数量N:1 ≤ N ≤ 100
学生的数量M:1 ≤ M ≤ 1000
查询的学生数量K:1 ≤ K ≤ M
学校的招生名额:1 ≤ 招生名额 ≤ 1000
学生的分数:总分 = 数学成绩 + 理综成绩 + 语文成绩 + 英语成绩
0 ≤ 数学成绩、语文成绩、英语成绩 ≤ 150
0 ≤ 理综成绩 ≤ 300
不会有两名考生总分和所有科目成绩都相同
学校和学生id: 1 ≤ id ≤ 100000，无重复

关于输出

K个整数，表示查询学生的录取结果，按查询顺序输出（-1表示未被录取）。

例子输入

2 2 2
10001 1
10003 1
1 750 150 300 150 150 10001 10003 -1
2 700 100 300 150 150 10001 10003 -1
2 1

例子输出

10003 10001

提示信息

样例解释:
根据总分，考生1的排名更高，首先考虑考生1的录取，其第一志愿为10001，而此时10001尚有1个名额，因此考生1录取至10001。其次考虑考生2的录取，其第一志愿为10001，但此时10001没有名额，第二志愿为10003，尚有1个名额，因此考生2录取至10003。

解题分析

作为典型的模拟题，本题其实并不难理解，只要模拟好过程即可。

1. 结构体定义：
   程序使用两个结构体school和student分别存储学校和学生的信息。school存储每个学校的ID和招生名额，student存储了每个学生的ID、各科成绩、选择的无论学校以及录取情况。

2. 输入处理：
   程序首先读取学校的数量N、学生的数量M和待查询学生的数量K。然后，按照输入格式，读取每所学校的信息，并存入schools数组。之后，读取每个学生的信息，并存入students数组。同时为待查询的学生ID做一个映射存入数组find1。

3. 排序：
   程序使用cmp函数对students数组进行降序排序，cmp函数在比较两个学生时，优先比较总分，如果总分相同，再比较数学成绩，如果数学成绩也相同，那么比较理综成绩，如果理综成绩也相同，那么比较语文成绩。

4. 模拟：
   程序按排序后的顺序，考虑每个学生的志愿，如果学生选择的学校还有名额，那么学生就会被录取，学校的名额减一，学生的录取情况记为学校的ID，这一过程使用一个三重循环实现。注意到，一旦学生被录取，就不再考虑他的其他志愿。

5. 输出：
   最后，程序查找每一个待查询的学生ID，并按照查询顺序输出他们的录取情况。如果一个学生没有被录取，输出为-1。

这段程序的时间复杂度主要是排序和模拟过程的时间复杂度，也就是O(MlogM + M*N)，其中M是学生的数量，N是学校的数量，对于最大测试数据，这个时间复杂度是可以接受的。

代码实现

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

struct school{
    int ID,count;
};

struct student{
    int ID,allScore,mathScore,phyScore,chineseScore,englishScore;
    int s[3];
    int lq;
};

bool cmp(student p1,student p2){
    if(p1.allScore>p2.allScore){
        return 1;
    }
    else if(p1.allScore<p2.allScore){
        return 0;
    }
    else{
        if(p1.mathScore>p2.mathScore) return 1;
        else if(p1.mathScore<p2.mathScore) return 0;
        else{
            if(p1.phyScore>p2.phyScore) return 1;
            else if(p1.phyScore<p2.phyScore) return 0;
            else{
                if(p1.chineseScore>p2.chineseScore) return 1;
                else if(p1.chineseScore<p2.chineseScore) return 0;
                else{
                    return 0;
                }
            }
        }
    }
}

school schools[105];
student students[1005];
int ID,count1,allScore,mathScore,phyScore,chineseScore,englishScore,s1,s2,s3;
int N,M,K;
int find1[1005];

int main() {
    scanf("%d%d%d",&N,&M,&K);
    for(int i=0;i<N;i++){
        scanf("%d%d",&ID,&count1);
        school temp={ID,count1};
        schools[i]=temp;
    }
    for(int i=0;i<M;i++){
        scanf("%d%d%d%d%d%d%d%d%d",&ID,&allScore,&mathScore,&phyScore
        ,&chineseScore,&englishScore,&s1,&s2,&s3);
        student temp={ID,allScore,mathScore,phyScore,chineseScore,englishScore,{s1,s2,s3},-1};
        students[i]=temp;
    }
    for(int i=0;i<K;i++){
        cin>>find1[i];
    }
    sort(students,students+M,cmp);
    for(int i=0;i<M;i++){
        for(int j=0;j<3;j++){
            for(int l=0;l<N;l++){
                if(schools[l].ID==students[i].s[j]){
                    if(schools[l].count>=1){
                        schools[l].count--;
                        students[i].lq=schools[l].ID;
                        break;
                    }
                }
            }
            if(students[i].lq!=-1) break;
        }
    }
    int flag=0;
    for(int i=0;i<K;i++){
        for(int j=0;j<M;j++){
            if(students[j].ID==find1[i]){
                if(flag==0){
                printf("%d",students[j].lq);
                flag=1;
                break;
                }
                else{
                printf(" %d",students[j].lq);
                break;
                }
            }
        }
    }
	return 0;
}