PAT (Advanced Level) Practice 1080 Graduate Admission

一、概述

以分数为第一优先，志愿为第二优先录取学生。

逻辑蛮麻烦，最开始理解错了题意，以为和高考一样，是先看第一志愿，再看第二志愿，没想到是先看分数，再看志愿。这导致浪费了很多时间。踩了不少坑，增加了许多经验。

二、分析

我只用了一个结构体，用来存储学生信息，学校信息本也可以用一个结构体的，我没用而是用一个二维数组代替。注意，二维数组过大，且在main函数中声明，会导致爆栈，抛出未经处理的异常，这时有两种方法解决，其一是在VS中更改工程属性，把默认堆栈保留大小变大点，但治标不治本，VS中不报错，oj中也会报段错误，实际上，只需要在main外声明数组即可。

由于我没有用结构体表示学校，因此用了许多数组。如下：

int schoolstu[100][40000] = { 0 };//放在main里会段错误，存储学生的ID
int school[100] = { 0 };
int schoolnow[100] = { 0 };
int schoollast[100] = { 0 };//每所学校招的最后一个人

分别储存各学校招的学生的初始序号，最大招生数量，目前招生数量和最后招的人。注意到一点，对结构体进行排序的话，结构体的初始序号最好另外保存一下，否则就会与排序后的角标弄混，该用初始序号的时候用当前角标，或者弄反，而且很难检查出来，我就是犯了这样一个错误，最开始没有用最后一个数组，而是直接用第一个数组中的元素对应，结果就出错了，很容易弄晕。

然后就是排序了，优先总分，其次是笔试分数，cmp可以这样写

bool cmp1(Student a, Student b)//总分排序
{
	if (a.sum != b.sum)
		return a.sum > b.sum;
	else if (a.GE != b.GE)
		return a.GE > b.GE;
	else return false;//不能返回0或者1或者true，会导致异常
}

注意这样写的时候最后返回的要是false，也可以这样写

bool cmp1(Student a, Student b)//总分排序
{
	if (a.sum != b.sum)
		return a.sum > b.sum;
	else 
		return a.GE > b.GE;
}

简单很多，推荐下面一种。

招生函数应该是最重要的了，如下，也是最容易出错的：

for (i = 0; i < N; i++)
	{
		for (n = 0; n < K; n++)
		{
			if (schoolnow[stu[i].choice[n]] < school[stu[i].choice[n]])//如果该学校还没招满
			{
				stu[i].admin = 1;//该学生被招入
				schoolstu[stu[i].choice[n]][schoolnow[stu[i].choice[n]]] = stu[i].ID;
				schoollast[stu[i].choice[n]] = i;
				schoolnow[stu[i].choice[n]]++;
				break;
			}
			else if (schoolnow[stu[i].choice[n]] >= school[stu[i].choice[n]]&& school[stu[i].choice[n]]!=0)//如果该学校刚好招满(只判断等于会有四个测试点过不去，加上大于有两个）
			{
				//if (stu[i].rank == stu
				//[
				//	schoolstu
				//		[stu[i].choice[n]]
				//	[school[stu[i].choice[n]] - 1]
				//].rank)//该学校招的最后一个学生名次和该生相同，因为schoolstu存储的是ID，所以不能这么写
				if(stu[i].rank == stu[schoollast[stu[i].choice[n]]].rank)
				{
					stu[i].admin = 1;//该学生被招入
					schoolstu[stu[i].choice[n]][schoolnow[stu[i].choice[n]]] = stu[i].ID;
					schoolnow[stu[i].choice[n]]++;
					break;
				}
			}
		}
	}

首先按总分排好序，这里就不赘述了，然后从第一名开始，从每个学生的第一志愿开始，看志愿学校招没招满，没招满就进该学校，修改对应数据，break；招满了就和最后招进去的一个人的排名对比，排名一样则你也进去，break；注意招满了的条件应该是当前学生大于等于最大招生，而且要保证最大值不为0，不能只有等于，那样不完全，也的确有可能有的学校不招生，都要考虑到。

最后输出即可。

三、总结

尽量不要有多层结构体嵌套，逻辑太难看清了，比如说这条逻辑错误的代码

if (stu[i].rank == stu
				[
					schoolstu
						[stu[i].choice[n]]
					[school[stu[i].choice[n]] - 1]
				].rank)
//这样分行写能好看点，但还是不清晰
//这样写
int m=stu[i].choice[n];
int n=school[m];
int k=schoolstu[m][n - 1];
if (stu[i].rank == stu[k].rank)
//虽然麻烦了点，但是可读性好得多

这在实际中是很有用的。

PS：代码如下：

#include<stdio.h>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>

//并不是志愿优先，而是分数优先，不然一号考生应录到学院2而不是学院5
//逻辑如下：先看分数最高的考生的志愿，优先报前面的志愿，报上了看考生二，也就是说，分高的三志愿也比分低的一志愿有竞争力

using namespace std;

struct Student
{
	int GE, GI;
	int sum;
	int choice[5] = { -1,-1,-1,-1,-1 };
	int rank = -1;
	int admin = 0;
	int ID;
}stu[40000];
int schoolstu[100][40000] = { 0 };//放在main里会段错误，存储学生的ID
bool cmp1(Student a, Student b)//总分排序
{
	if (a.sum != b.sum)
		return a.sum > b.sum;
	else if (a.GE != b.GE)
		return a.GE > b.GE;
	else return false;//不能返回0或者1或者true，会导致异常
}
bool cmpID(int a, int b)
{
	return a < b;
}
/*bool cmp2(Student a, Student b)//看第二三四五志愿
{
	if (a.admin != b.admin)
		a.admin < b.admin;
	else if (a.rank != b.rank)
		return a.rank < b.rank;
	else return false;
}*/

int main()
{
	int N, M, K;//总申请人数，总学校数，志愿数
	scanf("%d %d %d", &N, &M, &K);
	int i, j;
	int school[100] = { 0 };
	int schoolnow[100] = { 0 };
	int schoollast[100] = { 0 };//每所学校招的最后一个人
	for (i = 0; i < M; i++)
		scanf("%d", &school[i]);
	for (i = 0; i < N; i++)
	{
		scanf("%d %d", &stu[i].GE, &stu[i].GI);
		stu[i].sum = stu[i].GE + stu[i].GI;
		stu[i].ID = i;
		for (j = 0; j < K; j++)
			scanf("%d", &stu[i].choice[j]);
	}
	sort(stu, stu + N, cmp1);
	stu[0].rank = 0;
	for (i = 1; i < N; i++)
	{
		if (stu[i].sum == stu[i - 1].sum&&stu[i].GE == stu[i - 1].GE)
			stu[i].rank = stu[i - 1].rank;
		else
			stu[i].rank = i;
	}
	int n;
	for (i = 0; i < N; i++)
	{
		for (n = 0; n < K; n++)
		{
			if (schoolnow[stu[i].choice[n]] < school[stu[i].choice[n]])//如果该学校还没招满
			{
				stu[i].admin = 1;//该学生被招入
				schoolstu[stu[i].choice[n]][schoolnow[stu[i].choice[n]]] = stu[i].ID;
				schoollast[stu[i].choice[n]] = i;
				schoolnow[stu[i].choice[n]]++;
				break;
			}
			else if (schoolnow[stu[i].choice[n]] >= school[stu[i].choice[n]]&& school[stu[i].choice[n]]!=0)//如果该学校刚好招满(只判断等于会有四个测试点过不去，加上大于有两个）
			{
				//if (stu[i].rank == stu
				//[
				//	schoolstu
				//		[stu[i].choice[n]]
				//	[school[stu[i].choice[n]] - 1]
				//].rank)//该学校招的最后一个学生名次和该生相同，因为schoolstu存储的是ID，所以不能这么写
				if(stu[i].rank == stu[schoollast[stu[i].choice[n]]].rank)
				{
					stu[i].admin = 1;//该学生被招入
					schoolstu[stu[i].choice[n]][schoolnow[stu[i].choice[n]]] = stu[i].ID;
					schoolnow[stu[i].choice[n]]++;
					break;
				}
			}
		}
	}
	/*int n;
	for (n = 1; n < K; n++)
	{
		sort(stu, stu + N, cmp2);
		for (i = 0; i < N; i++)
		{
			if (stu[i].admin == 0)
			{
				if (schoolnow[stu[i].choice[n]] < school[stu[i].choice[n]])//如果该学校还没招满
				{
					stu[i].admin = 1;//该学生被招入
					schoolstu[stu[i].choice[n]][schoolnow[stu[i].choice[n]]] = stu[i].ID;
					schoolnow[stu[i].choice[n]]++;
				}
				else if (schoolnow[stu[i].choice[n]] == school[stu[i].choice[n]])//如果该学校刚好招满
				{
					if (stu[i].rank == stu[
						schoolstu
							[stu[i].choice[n]]
						[school[stu[i].choice[n]] - 1]
					].rank)//该学校招的最后一个学生名次和该生相同
					{
						stu[i].admin = 1;//该学生被招入
						schoolstu[stu[i].choice[n]][schoolnow[stu[i].choice[n]]] = stu[i].ID;
						schoolnow[stu[i].choice[n]]++;
					}
				}
			}
		}
	}
	*/
	for (i = 0; i < M; i++)
	{
		if (schoolnow[i] == 0)
			printf("\n");//换行前面不要加空格
		else
		{
			sort(schoolstu[i], schoolstu[i] + schoolnow[i], cmpID);
			for(j = 0; j < schoolnow[i] - 1;j++)
			{
				printf("%d ", schoolstu[i][j]);
			}
			printf("%d\n", schoolstu[i][j]);
		}
	}
}