1553 - Graduate Admission

通过次数

提交次数

旧版界面

时间限制 : 1 秒内存限制 : 32 MB

It is said that in 2011, there are 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:

<span style="font-size:12.0pt;font-family:&quot;color:#333333;background:white;">&nbsp;&nbsp;&nbsp; • The applicants are ranked according to their final grades, and will be admitted one by one from the top of the rank list.<br />

    • 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.

<br />

题目输入

Each input file may contain more than one test case.

      Each case starts with a line containing three positive integers: N (≤40,000), the total number of applicants; M (≤100), the total number of graduate schools; and K (≤5), the number of choices an applicant may have.
      In the next line, separated by a space, there are M positive integers. The i-th integer is the quota of the i-th graduate school respectively.
      Then N lines follow, each contains 2+K integers separated by a space. The first 2 integers are the applicant's GE and GI, respectively. The next K integers represent the preferred schools. For the sake of simplicity, we assume that the schools are numbered from 0 to M-1, and the applicants are numbered from 0 to N-1.

<br />

题目输出

For each test case you should output the admission results for all the graduate schools. The results of each school must occupy a line, which contains the applicants' numbers that school admits. The numbers must be in increasing order and be separated by a space. There must be no extra space at the end of each line. If no applicant is admitted by a school, you must output an empty line correspondingly.

输入/输出样例

输入格式

11 6 3
2 1 2 2 2 3
100 100 0 1 2
60 60 2 3 5
100 90 0 3 4
90 100 1 2 0
90 90 5 1 3
80 90 1 0 2
80 80 0 1 2
80 80 0 1 2
80 70 1 3 2
70 80 1 2 3
100 100 0 2 4

输出格式

C语言解答

#include <stdio.h>

#define equal(a, b) (grades[a][0] == grades[b][0])&&(grades[a][1] == grades[b][1])

int cap[100], rank[40000], grades[40000][10] = { 0 }, acc[100][40000];
int n, m, k;

void RankG() {
	int i, j, k, flags, t, p, q;
	for(i = 0; i < n; i++)
		for (j = i + 1; j < n; j++) {
			flags = 0;
			p = rank[i];
			q = rank[j];
			if (grades[p][0] < grades[q][0]) {
				flags = 1;
			}
			else if((grades[p][0] == grades[q][0])&&(grades[p][1]<grades[q][1]))
			{
				flags = 1;
			}
			if (flags) {
				t = rank[i];
				rank[i] = rank[j];
				rank[j] = t;
			}
		}
}

void buble(int as[], int ns) {
	int i, j, t;
	for(i = 1; i < ns; i++)
		for (j = i + 1; j <= ns; j++) {
			if (as[i] > as[j]) {
				t = as[i];
				as[i] = as[j];
				as[j] = t;
			}
		}
}

int main() {
	int i, j, index, school;
	while (scanf("%d %d %d", &n, &m, &k) != EOF) {
		for (i = 0; i < m; i++) {
			scanf("%d", &cap[i]);
			acc[i][0] = 0;
		}
		for (i = 0; i < n; i++) {
			rank[i] = i;
			for (j = 1; j < k + 3; j++)
				scanf("%d", &grades[i][j]);
			grades[i][0] = grades[i][1] + grades[i][2];
		}
		RankG();		
		for (i = 0; i < n; i++) {
			index = rank[i];
			for (j = 3; j < k + 3; j++) {
				school = grades[index][j];
				if (cap[school] > acc[school][0]) {
					acc[school][0]++;
					acc[school][acc[school][0]] = index;
					break;
				}
				else if(equal(acc[school][acc[school][0]], index))
				{
					acc[school][0]++;
					acc[school][acc[school][0]] = index;
					break;
				}
			}
		}
		for (i = 0; i < m; i++) {
			buble(acc[i], acc[i][0]);
			for (j = 1; j <= acc[i][0]; j++) {
				printf("%d", acc[i][j]);
				if (j < acc[i][0])printf(" ");
			}
			printf("\n");
		}
	}
}

C++解答

#include <cstdio>
#include <algorithm>
using namespace std;

// 定义每个考生的信息结构
struct StuType{
    double ge, gi, a;	// 统考分数、面试分数，以及均分
    int id;		// 考生的序号
    int s[5];	// 考生选择的学校（最多 5 个）
};

// 定义比较函数，用来对考生信息进行排序
bool cmp(StuType a, StuType b){
    if(a.a == b.a){				// 如果均分相同
        return a.ge > b.ge;		// 则比较统考分数
    }
    return a.a > b.a;			// 否则比较均分
}

int schools[110][44000];		// 记录学校招收的考生序号
StuType students[44000];		// 记录所有的考生信息

int main(){

    int n;
    while(scanf("%d",&n) != EOF){	// 读取考生数目
        int m, k;
        scanf("%d%d", &m, &k);		// 读取学校数目以及考生可选学校的数目
        int numOfSchool[110];		// 存储每个学校能够招收考生的数目
        for(int i=0;i<m;i++){
            scanf("%d",&numOfSchool[i]);	// 读取每个学校能够招收考生的数目
        }
        for(int i=0;i<n;i++){
            scanf("%lf%lf", &students[i].ge, &students[i].gi);	// 读取考生统考成绩以及面试成绩
            students[i].a = (students[i].ge+students[i].gi)/2;	// 计算统考成绩和面试成绩的均分
            for(int j=0;j<k;j++){
                scanf("%d",&students[i].s[j]);		// 读入考生选取的学校序号
            }
            students[i].id = i;		// 记录考生的序号
        }
        sort(students, students+n, cmp);	// 按先均分后统考分数的顺序进行排序
        int numOfSche[110] = {0};			// 记录每个学校已经招收的考生
        double gradeOfLast[110][2];			// 如果需要扩招的话，记录扩招时需要的均分和统考分数，
											// 因为只有均分和统考分数不小于（实际上是相等）扩招时才能够被扩招
        for(int i=0;i<n;i++){				// 对每个考生进行遍历
            for(int p=0;p<k;p++){			// 遍历考生选择的每个学校
                int j = students[i].s[p];	// 获得考生选择学校的编号
                if(numOfSche[j]<numOfSchool[j]){	// 判断目前该学校是否招生已满，如果没满，则招收之
                    schools[j][numOfSche[j]++] = students[i].id;	// 记录学校招收考生的序号
                    if(numOfSche[j] == numOfSchool[j]){				// 如果正好招生已满，
                        gradeOfLast[j][0] = students[i].a;			// 则记录最后一个考生的均分
                        gradeOfLast[j][1] = students[i].ge;			// 以及统考分
                    }
                    break;		// 注意，一旦考生被选择的某个学校录取了，后面的学校就不能再录取了
                }else if(students[i].a==gradeOfLast[j][0] && students[i].ge==gradeOfLast[j][1]){	// 如果招生已满，则判断该考生的均分和统考分是否与最后一名相同，如果相同则应当扩招进来
                    schools[j][numOfSche[j]++] = students[i].id;	// 记录学校招收考生的序号
                    break;
                }
            }
        }
        for(int i=0;i<m;i++){		// 将学校的考生信息输出
            sort(schools[i], schools[i]+numOfSche[i]);	// 注意要求按考生序号递增输出
            for(int j=0;j<numOfSche[i];j++){
                if(j){				// 除了第一个考生序号前面不需要输出空格，后面的需要前面都需要输出一个空格
                    putchar(' ');
                }
                printf("%d",schools[i][j]);	// 输出考生序号
            }
            putchar('\n');
        }
    }

    return 0;
}

上一题下一题提示代码讨论统计