[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
投递大连飞创信息技术有限公司等公司10个岗位
