1080. Graduate Admission (30)

思路

首先用结构体app来维护申请,school来维护学校的限额以及已经录取的app id;
对于每一个申请,按照其志愿顺序查看对应学校的情况;
如果,该申请人的排名和该学校上一个录取的申请人的排名一样,那么录取该名申请人;
否则,检查学校限额,如果没有达到限额则录取该申请人,并更新学校结构体的相关信息;

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,k;

struct app
{
    int id,ge,gi;
    float avg;
    int rank;
    vector<int> perfer;
    app(int d,int e,int i,vector<int> p):
    id(d),ge(e),gi(i),perfer(p)
    {
        avg = (double)(ge+gi)/1.0*2;
    }
};
struct school
{
    int lastrank,quota;
    vector<int> admit;
    school(int q):quota(q),lastrank(-1){}
};
vector<app> apps;
vector<school> schools;
int cmp(const app& a, const app& b)
{
    if(a.avg == b.avg) 
        return a.ge > b.ge;
    return a.avg > b.avg;
}
int main()
{
    cin>>n>>m>>k;
    int q;
    for(int i=0;i<m;i++){

       cin >> q;
        school tmp(q);
        schools.push_back(tmp);
    }
    int ge,gi,p;
    for(int i=0;i<n;i++){

       cin>>ge>>gi;
        vector<int> prefer;
        for(int j=0;j<k;j++){
            cin>>p;
            prefer.push_back(p);
        }
        app tmp(i,ge,gi,prefer);
        apps.push_back(tmp);
    }
    sort(apps.begin(),apps.end(),cmp);
    apps[0].rank=0;
    for(int i=1;i<apps.size();i++) {

        if(apps[i].avg == apps[i-1].avg && apps[i].ge == apps[i-1].ge)
        {
            apps[i].rank = apps[i-1].rank;
        }
        else
            apps[i].rank = i;
    }
    for(int i=0;i<apps.size();i++) 
    {

        for(int j=0;j<apps[i].perfer.size();j++) 
        {

            int perf = apps[i].perfer[j];
            if(apps[i].rank == schools[perf].lastrank) 
            {
                schools[perf].admit.push_back(apps[i].id);
                break;
            }
            else
            {
                if(schools[perf].quota > schools[perf].admit.size()) 
                {
                    schools[perf].admit.push_back(apps[i].id);
                    schools[perf].lastrank = apps[i].rank;
                    break;
                }
            }
        }
    }
    for(int i=0;i<schools.size();i++) 
    {

        sort(schools[i].admit.begin(),schools[i].admit.end()); 
        for(int j=0;j<schools[i].admit.size();j++)
        {
            cout<<schools[i].admit[j];
            if(j != schools[i].admit.size()-1) cout<<" ";
        }
        cout<<endl;
    }
    return 0;
}