1080 Graduate Admission (30分)

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 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:

0 10
3
5 6 7
2 8

1 4

题目描述：学校录取学生的模拟过程

输入：第一行n，m，k。分别为学生人数，学校数，学生可填报志愿数。第二行m个值，分别表示学校录取的人数。接下来n行，为学生的考试成绩GE，GI，以及填报的k个学校。

输出：每个学校录取的学生编号，从小到大输出。

录取规则：成绩排序，总分=（GE+GI）/2，总分高排在前面；当总分相同时，GE成绩高排在前面；当总分和GE都相同时，排名并列。如果学校最后录取的学生有多名排名是一样的，超额也要将他们都录取了。

解题思路：模拟题，很容易就把简单的问题复杂化了。先将学生按照成绩排序，分高的选择权。可以从第一名开始按其意愿选择学校，当他选择的学校没有录取满人时，他就会直接被学校录取，当学校录取满人了，其他成绩比较低的就无法再进入这满了人的学校，只能看其他志愿。

注意：在学校最后录取的学生成绩/排名不唯一时，怎么把排名相同的全部录取？这需要将学校最后录取的人的分数记录下来，就两个数组记录一下就行了。

模拟题得多做几道，找找感觉！

#include<bits/stdc++.h>
using namespace std;
const int maxn = 40000+5;
int n, m, k, snum[200], ltsum[200], ltge[200];
bool vis[maxn];
struct node{
	int ge, gi, id, sum;
	vector<int> sc;
	bool operator <( const node &x )const{
        if( sum!=x.sum ) return sum > x.sum;
        return ge > x.ge;
    }
};
vector<int> ans[200];
vector<node> v;
//bool cmp(node a, node b){
//	if(a.sum!=b.sum) return a.sum > b.sum;
//	else return a.ge > b.ge;
//}
int main()
{
	int g;
	memset(vis,true,sizeof(vis));
	scanf("%d %d %d", &n, &m, &k);
	for(int i=0; i<m; i++) scanf("%d", &snum[i]);
	for(int i=0; i<n; i++){//学生 
		node t;
		scanf("%d %d", &t.ge, &t.gi);
		t.id = i; t.sum = t.ge+t.gi;
		for(int j=0; j<k; j++){
			scanf("%d", &g);
			t.sc.push_back(g);//学生报志愿 
		}
		v.push_back(t);
	}
//	sort(v.begin(),v.end(),cmp);
	sort(v.begin(), v.end());
	for(int i=0; i<n; i++){
		node t = v[i];
		for(int j=0; j<k; j++){
			int cid = t.sc[j];
			if(!vis[t.id]) continue;
			if(ans[cid].size()<snum[cid]){
				ltsum[cid] = t.sum;
				ltge[cid] = t.ge;
				ans[cid].push_back(t.id);
				vis[t.id] = false;
			}
			else if(t.sum==ltsum[cid]&&t.ge==ltge[cid]){
				ans[cid].push_back(t.id);
				vis[t.id] = false;
			}
		}
	}
	for(int i=0; i<m; i++){
		sort(ans[i].begin(),ans[i].end());
		for(int j=0; j<ans[i].size(); j++){
			if(j) printf(" ");
			printf("%d", ans[i][j]);
		}
		printf("\n");
	}
	return 0;
}