PAT-1080 Graduate Admission （结构体排序）

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 G_E, and the interview grade G_I. The final grade of an applicant is (G_E + G_I) / 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 G_E. 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.

Input Specification:

Each input file contains 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 G_E and G_I, 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.

Output Specification:

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.

Sample Input:

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

Sample Output:

题目大意：学生申请学校的问题，有n个学生，m所学校，每个学生最多填报的志愿数为k，给出这m所学校的名额数。每个学生有GE和GI两门成绩，平均成绩高的则排在前面；若相等，则GE高的排在前面；再相等则排名相同。对于排名相同的学生，即使名额不够了也会一并接受，接着给出每个学生填报的k个学校的序号。要求输出每个学校最终招到的学生的序号。

主要思路：1. 建立包含每个学生的结构体数组，每个结构体包括学生的序号id，两项成绩gi和ge，以及一个含有其报名学校的数组；以一个二维的vector容器存放每个学校招收的学生，另用一个数组存放每个学校当前剩余的名额；

2. 成绩好的先选。按照成绩排序结构体数组，然后从前到后让每个学生依次选择学校，如果当前志愿学校名额>0，则被录取，该学校的名额数-1；如果名额=0，则与该学校已录取的最后一个学生比较，如果两人两门成绩分别相同，则该生被录取，否则考虑下一个志愿。注意要对每一个学校录取的学生的序号排序后再输出。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct info {
	int id;				//申请者序号（防止因排序打乱）
    int ge, gi;
    int school[5];		//申请者志愿
} applicant;
applicant a[40000];
int quota[100];
bool comp(applicant v, applicant w);
bool comp_id(applicant v, applicant w);

int main(void) {
    int n, m, k, i, j;
    
    cin >> n >> m >> k;
	vector<vector<applicant> > vec(m);			
    for (i = 0; i < m; i++)
        cin >> quota[i];
    for (i = 0; i < n; i++) {
		a[i].id = i;
        cin >> a[i].ge >> a[i].gi;
        for (j = 0; j < k; j++)
            cin >> a[i].school[j];                  
    }
    sort(a, a + n, comp);
    for (i = 0; i < n; i++) {
        for (j = 0; j < k; j++) {
            int id = a[i].school[j];						//成绩排行第i的申请者的第j个志愿的学校
            if (quota[id] > 0) {
                vec[id].push_back(a[i]);    
                quota[id]--;
                break;
            }
            else if (quota[id] == 0) {
				applicant t = vec[id].back();				//序号为id的学校录取的成绩最低的同学
				if (a[i].ge == t.ge && a[i].gi == t.gi) {	//成绩完全相同才说明排名相同
				    vec[id].push_back(a[i]);
					break;						
				}
            }
        }
    }
    for (i = 0; i < m; i++) {
        if (vec[i].size() == 0) {
            cout << "
";
            continue;
        }
		sort(vec[i].begin(), vec[i].end(), comp_id);		//对容器中的学生序号进行排序
        cout << vec[i][0].id;
        for (j = 1; j < vec[i].size(); j++)
            cout << " " << vec[i][j].id;
        cout << endl;
    }       	

	return 0;
}
//按成绩排序
bool comp(applicant v, applicant w) {
	if (v.ge + v.gi == w.ge + w.gi)
		return v.ge > w.ge;
    return (v.ge + v.gi) > (w.ge + w.gi);  
}
//按序号排序
bool comp_id(applicant v, applicant w) {
	return v.id < w.id;
}