PAT 解题报告 1080. Graduate Admission (30)

1080. Graduate Admission 题目描述:

It is said that in 2013, there were about 100 graduate schools ready to proceed over 40,000 applications in Zhejiang Province. It would help a lot if you could write a program to automate the admission procedure.

Each applicant will have to provide two grades: the national entrance exam grade GE, and the interview grade GI. The final grade of an applicant is (GE + GI) / 2. The admission rules are:

  • The applicants are ranked according to their final grades, and will be admitted one by one from the top of the rank list.
  • If there is a tied final grade, the applicants will be ranked according to their national entrance exam grade GE. If still tied, their ranks must be the same.
  • Each applicant may have K choices and the admission will be done according to his/her choices: if according to the rank list, it is one’s turn to be admitted; and if the quota of one’s most preferred shcool is not exceeded, then one will be admitted to this school, or one’s other choices will be considered one by one in order. If one gets rejected by all of preferred schools, then this unfortunate applicant will be rejected.
  • If there is a tied rank, and if the corresponding applicants are applying to the same school, then that school must admit all the applicants with the same rank, even if its quota will be exceeded.

题目要求模拟研究生考试的录取过程, 输入学生成绩, 学生志愿, 得到录取结果(输出各个学校招收的学生名单).

学生成绩分成两部分, 笔试成绩ge, 面试成绩gi, 排名先按照总分排, 总分相同则按照ge排. 录取过程按照排名顺序进行. 这题的难点在第四条录取的规则, 意思是说如果有多个排名想通的考生同时选择了同一所学校. 不管有没有超过这个学校的录取名额, 这些学生都要被录取进入这所学校. 清楚了题目意思, 且看下面的算法分析, 第四条规则我会好好讲讲(只能说PAT真心坑>_<).

1080. Graduate Admission 算法分析:

算法无非是先给学生按照规则里面说的成绩排好序, 然后对每个学生挨个依次寻找可以接受这个学生的学校(根据这个学生的K个志愿).  但是由于第四条规则的存在, 当发现当前学生A1因为当前录取学校B名额已满而不能被当前志愿学校录取的时候, 我们还要多一步检查, 以防”漏网之鱼”: 由于第四条规则, 我们不能直接判定学生A1不能被学校B录取, 因为有可能存在同排名的其他学生(比如我们叫他A2)也要选这个学校B, 这个时候学生A1和A2都应该被录取进入这所学校B. 这里有个前提: 就是此时学校B至少还要有一个录取名额, 笔者的潜台词就是如果此时B已经是录取完毕, 没有名额了, 那么A1, A2还是不能同时被学校B录取.  这个前提说难想到么也不是特别难想到, 笔者这么提出来了, 再想想也是很自然的一件事情, 你说我这个学校还有一个名额的时候, 两个相同排名的学生都选择我这个学校, 我只能两个都录取才对他们都公平, 要是到了他们选则的时候, 我这个学校名额已经满了, 那么他们都没有机会进入我这个学校。 这里不得不吐槽PAT的题目描述, 实在有时候令人费解, (或者我只能说笔者我自己也是智商拙计…..), 我觉得这种OJ题目, 题目应该越清楚越好, 考生应该花时间花心思在算法本身上面做文章而不是揣测题意. 再回到题目本身, 红色字体标出的前提是很重要的前提, 我下面的代码的正确性就是基于这个前提的, 否则这个case: 学生a, b, c每个人都有一个志愿可以填, 总共有两所学校D, E, 这两所学校的录取名额都是1, 排名是a排名第一, b和c并列第二, 然后这三个人的志愿都是学校E, 那么结果其实应该是只有a被E录取, b和c都会被reject. 笔者一开始对题意的理解就是, 首先a被E录取了, 然后到了b和c, 虽然已经超过E的录取名额, 但是有第四条规则, b和c还是可以被E录取. 这个理解是不对的, 这样的理解也是写不出代码的, 本身这样的逻辑就使得代码逻辑非常复杂. 如果遇到这样的情况, 考生可能要再重新审视一下题意了. 下面是可以AC的代码:

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

struct Node {
	int ge;
	int gi;
	int tol;
	int id;
};

bool cmp(const Node &a, const Node &b) {
	if( a.tol != b.tol )
		return a.tol > b.tol;
	return a.ge > b.ge;
}

int quota[103];
Node applicants[40005];
int admit[40005];
int preferredSchools[40005][6];
std::vector<int> schoolEnrolled[103];

int main() {
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 0; i < m; ++i) scanf("%d", &quota[i]);
	for(int i = 0; i < n; ++i) {
		scanf("%d %d", &(applicants[i].ge), &(applicants[i].gi) );
		applicants[i].id = i;
		applicants[i].tol = applicants[i].gi + applicants[i].ge;
		for(int j = 0; j < k; ++j)
			scanf("%d", &preferredSchools[i][j]);
	}
	std::sort(applicants, applicants + n, cmp);
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < k; ++j) {
			int schoolChoice = preferredSchools[applicants[i].id][j];
			if( quota[schoolChoice] > 0) {
				admit[i] = schoolChoice;
				schoolEnrolled[schoolChoice].push_back(applicants[i].id);
				quota[schoolChoice]--;
				break;
			}
			if( i > 0 && admit[i - 1] == schoolChoice &&
				applicants[i - 1].ge == applicants[i].ge &&
                                applicants[i - 1].gi == applicants[i].gi) {
				admit[i] = schoolChoice;
				schoolEnrolled[schoolChoice].push_back(applicants[i].id);
				quota[schoolChoice]--;
				break;
			}
		}
	}
	for(int i = 0; i < m; ++i) {
		if(schoolEnrolled[i].empty()) {
			printf("\n");
			continue;
		}
		sort(schoolEnrolled[i].begin(), schoolEnrolled[i].end());
		for(int j = 0; j < schoolEnrolled[i].size(); ++j) {
			if(j == 0)
				printf("%d", schoolEnrolled[i][j]);
			else
				printf(" %d", schoolEnrolled[i][j]);

		}
		printf("\n");
	}
	return 0;
}

1080. Graduate Admission 注意点:

这题的第四个(index start from 0)测试用例容易引起超时, 笔者揣测(因为没法做单一变量的对比试验……)如下可能的一些引起超时的原因:

(1) 使用scanf, printf不要使用cin, cout

(2) 最后输出每个学校的录取名单的时候不要用set存学生列表, 用vector

(3) 如果有可能尽量时候定长的数组, 不适用边长的STL的容器

(4) 用变量记录下学生的总分, 而不是每次都去online地计算ge + gi

Written on May 2, 2014