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:
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
题目大意:将每个学生按照成绩排序,然后根据学生的意向学校去投递, 如果意向学校已经满了,继续投递; 输出每个学校录取的学生编号
思路:建立两个struct, sch:记录学校要录取的人数, 最后一个录取学生的名次, 以及录取学生的数组; node:记录学生的成绩,编号,意向学校;
通过学生成绩依次按照每个学生的意向学校去探测意向学校是否能投递, 能投递则把学生添加到相应的学校中, 对每个学校录取的学生排序后输出;
注意点:1.对于需要排序的结构数据,一般应该在结构中记录数据的编号; 2.正确放置break点
1 #include<iostream> 2 #include<vector> 3 #include<algorithm> 4 using namespace std; 5 struct node{ 6 int ge, gi, final, rank, id; 7 int choice[5]; 8 }; 9 10 struct sch{ 11 int quota, lastrank; 12 vector<int> admit; 13 }; 14 15 bool cmp(node a, node b){ 16 if(a.final!=b.final) return a.final>b.final; 17 return a.ge>b.ge; 18 } 19 20 int main(){ 21 int n, m, k, i, j; 22 vector<sch> school(100); 23 vector<node> application; 24 cin>>n>>m>>k; 25 for(i=0; i<m; i++) cin>>school[i].quota; 26 for(i=0; i<n; i++){ 27 node nnode; 28 cin>>nnode.ge>>nnode.gi; 29 nnode.final=(nnode.ge+nnode.gi)/2; nnode.id=i; 30 for(j=0; j<k; j++) cin>>nnode.choice[j]; 31 application.push_back(nnode); 32 } 33 sort(application.begin(), application.end(), cmp); 34 application[0].rank=1; 35 int rank=1; 36 for(i=1; i<n; i++){ 37 if(application[i].final==application[i-1].final && application[i].ge==application[i-1].ge) application[i].rank=rank; 38 else{rank=i+1; application[i].rank=rank;} 39 } 40 for(i=0; i<n; i++){ 41 for(j=0; j<k; j++){ 42 int index=application[i].choice[j]; 43 if(school[index].quota>0){ 44 school[index].quota--; 45 school[index].lastrank = application[i].rank; 46 school[index].admit.push_back(application[i].id); 47 break; 48 }else if(school[index].quota==0 && application[i].rank==school[index].lastrank){ 49 school[index].admit.push_back(application[i].id); 50 break; 51 } 52 } 53 } 54 55 for(i=0; i<m; i++){ 56 sort(school[i].admit.begin(), school[i].admit.end()); 57 for(j=0; j<school[i].admit.size(); j++){ 58 if(j==0) cout<<school[i].admit[j]; 59 else cout<<" "<<school[i].admit[j]; 60 } 61 cout<<endl; 62 } 63 return 0; 64 }
原文:https://www.cnblogs.com/mr-stn/p/9182384.html