关于算法-数据结构:PAT甲级1080-Graduate-Admission

题目粗心：

有 N 位考生，M 所学校，每位考生都有 K 个意愿学校，每个学校也有招生人数限度。当初给出所有考生的初试问题 GE、面试问题 GI 以及 K 个意愿学校的编号，要求模仿学校录取招生的过程，并输入每个学校录取的考生编号 (按从小到大程序)。

排序规定:

 先按考生的总分 (GE + GD)/ 2 从高到低排序，总分雷同的按 GE 从高到低排序。如果 GE 依然雷同，则按排名雷同解决。

算法思路：

首先得定义好数据的构造，不便解决，这里采纳构造体 Applicant 保留每一位考生的 id,GE,GI, 总分, 排名和意愿信息，并且应用数组 vector<Applicant> schools[M] 记录每一个学校录取的学生，这里对于总分间接采纳 GE+GI 的解决，无需除以 2。顺次将所有数据进行输出后，对所有的学生进行排序，而后获取排名，再依照排名的程序遍历每一个学生的每一个意愿，只有以后填写的意愿学校没有招满或者最初一个学生的排名等于以后学生的排名就能够录取，这里得留神录取后得退出循环不得在进行解决。最初依照要求输入，得留神每一个学校录取的考生的编号是依照从小到大进行输入的。

提交后果：

AC 代码：

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

struct Applicant{
    int id;
    int GE;
    int GI;
    int final_grade;
    int rank;
    int preferred_schools[6];
};

bool cmp(Applicant a,Applicant b){if (a.final_grade!=b.final_grade){return a.final_grade>b.final_grade;} else {return a.GE>b.GE;}
}

bool cmpById(Applicant a,Applicant b){return a.id<b.id;}

int main(){
    int N,M,K;// 总人数, 学校数目，每一个学生的意愿数目
    scanf("%d %d %d",&N,&M,&K);
    int quota[M];// 每一个学校的名额
    for (int i = 0; i < M; ++i) {scanf("%d",&quota[i]);
    }
    vector<Applicant> applicants;// 保留所有学生
    Applicant applicant;
    for (int j = 0; j < N; ++j) {scanf("%d %d",&applicant.GE,&applicant.GI);
        applicant.final_grade = applicant.GE+applicant.GI;
        applicant.id = j;
        for (int i = 0; i < K; ++i) {scanf("%d",&applicant.preferred_schools[i]);
        }
        applicants.push_back(applicant);
    }
    sort(applicants.begin(),applicants.end(),cmp);
    // 获取排名
    for (int k = 0; k < applicants.size(); ++k) {if(k==0){applicants[k].rank = 1;
        } else if (applicants[k].final_grade==applicants[k-1].final_grade&&applicants[k].GE==applicants[k-1].GE){applicants[k].rank = applicants[k-1].rank;
        } else {applicants[k].rank = k+1;
        }
    }
    vector<Applicant> schools[M];// 每一个学校录取的学生
    // 解决每一个考生的意愿
    for (int l = 0; l < applicants.size(); ++l) {
        // 遍历所有的意愿
        for (int i = 0; i < K; ++i) {int preferred = applicants[l].preferred_schools[i];
            // 首先判断该学校是否招满了
            if(schools[preferred].size()<quota[preferred]||schools[preferred][schools[preferred].size()-1].rank==applicants[l].rank){
                // 没有满，间接招或学校招满了，然而该学生和最初一名排名雷同，也招
                schools[preferred].push_back(applicants[l]);
                break;
            } 
        }
    }
    for (int m = 0; m < M; ++m) {
        // 招到学生才进行解决
        if (schools[m].size()>0){sort(schools[m].begin(),schools[m].end(),cmpById);
            for (int i = 0; i < schools[m].size(); ++i) {printf("%d",schools[m][i].id);
                if (i<schools[m].size()-1) printf(" ");
            }
        }
        printf("\n");
    }
    return 0;
}