[PAT解题报告] Graduate Admission

其实这个题也不难，算作模拟题吧。给定若干个学校，若干个学生。每个学校有一定的招生名额，每个学生可以报一些志愿，志愿分先后，表示他想去的学校。规则：

（1）每个学生有两个成绩，根据平均分，和一门成绩对学生进行排序——平均分越高则学生越好，平均分相同，第一门课越高则越好，否则学生排名相同。这里需要说一句，其实按平均分排和按总分排是一样的，不用真的除以2。

（2）每个学校有一定名额，按照学生志愿，优先录取好的学生，但是如果学校录取了某个学生，还有一个和他一样好的学生也报了这个学校，则学校也应该录取他，即使录取他会使人数已经超过了学校的名额。

（3）学生按照志愿选取学校。

做法：先对学生排序，好的学生优先。一次看每个学生的每个志愿，看看学校能不能录取。录取原则是关键：

（a) 如果学校没录取满，显然要这个学生——因为他是目前最好的了，更好的已经都录取完了

（b) 如果学校录取的人数已经超额，则要看最后一个录取的学生（最差的）和现在这个是不是一样好，如果一样好，则必须要。

按照这个规则模拟就好了。输出学校录取的学生的时候，别忘记按照id再排序一次。

代码：

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

pair<int,int> student[40004];
int want[40004][5];
vector<int> school[102];
int id[40004];
int c[102];

bool cmp(const int &a,const int &b) {
    return student[a] > student[b];
}

int main() {
int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for (int i = 0; i < m; ++i) {
        scanf("%d",c + i);
    }
    for (int i = 0; i < n; ++i) {
        scanf("%d%d",&student[i].second,&student[i].first);
        id[i] = i;
        student[i].first += student[i].second;
        for (int j = 0; j < k; ++j) {
            scanf("%d",&want[i][j]);
        }
    }
    sort(id, id + n, cmp);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < k; ++j) {
            if ((c[want[id[i]][j]] > school[want[id[i]][j]].size()) || (student[school[want[id[i]][j]].back()] == student[id[i]])) {
                school[want[id[i]][j]].push_back(id[i]);
                break;
            }
        }
    }
    for (int i = 0; i < m; ++i) {
        sort(school[i].begin(),school[i].end());
        for (int j = 0; j < school[i].size(); ++j) {
            if (j) {
                putchar(' ');
            }
            printf("%d",school[i][j]);
        }
        puts("");
    }
    return 0;
}

原题链接： http://www.patest.cn/contests/pat-a-practise/1080