PAT甲级1080 Graduate Admission【模拟】

题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805387268571136

题意：

模拟高考志愿录取。

考生根据总成绩和高考成绩排名。根据排名往下录取，每个人有k个志愿。

如果他填的学校名额没有满，那么就可以被录取。如果他填的学校名额满了，最后一名的排名和这个人是一样的话，就可以被录取。

思路：

直接模拟。

刚开始居然有一个数据超时了，把排序的cmp里面改成传引用居然就过了。

 1 //#include<bits/stdc++>
 2 #include<stdio.h>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<stdlib.h>
 7 #include<queue> 
 8 #include<map>
 9 #include<stack>
10 #include<set>
11 
12 #define LL long long
13 #define ull unsigned long long
14 #define inf 0x3f3f3f3f 
15 
16 using namespace std;
17 
18 int n, m, k;
19 const int maxn = 4e4 + 5;
20 struct student{
21     int ge, gi;
22     int id; 
23     int gfinal;
24     vector<int>apply;
25 }stu[maxn];
26 
27 bool cmp(student &a, student &b)
28 {
29     if(a.gfinal == b.gfinal){
30         return a.ge > b.ge;
31     }
32     else return a.gfinal > b.gfinal;
33 }
34 
35 struct school{
36     int quota;
37     vector<student>addmit;
38 }sch[105]; 
39 
40 bool cmpans(student &a, student &b)
41 {
42     return a.id < b.id;
43 }
44 
45 
46 int main()
47 {
48     scanf("%d%d%d", &n, &m, &k);
49     for(int i = 0; i < m; i++){
50         scanf("%d", &sch[i].quota);
51     }
52     for(int i = 0; i < n; i++){
53         stu[i].id = i;
54         scanf("%d%d%", &stu[i].ge, &stu[i].gi);
55         stu[i].gfinal = (stu[i].ge + stu[i].gi) / 2;
56         for(int j = 0; j < k; j++){
57             int s;
58             scanf("%d", &s);
59             stu[i].apply.push_back(s);
60         }
61     }
62     sort(stu, stu + n, cmp);
63     
64     for(int i = 0; i < n; i++){
65         for(int j = 0; j < k; j++){
66             int s = stu[i].apply[j];
67             if(sch[s].quota){
68                 sch[s].addmit.push_back(stu[i]);
69                 sch[s].quota--;
70                 break;
71             }
72             else{
73                 if(sch[s].addmit.size()){
74                     student lastone = sch[s].addmit.back();
75                     if(lastone.gfinal == stu[i].gfinal && lastone.ge == stu[i].ge){
76                         sch[s].addmit.push_back(stu[i]);
77                         break;
78                     }
79                 }
80             }
81         }
82     }
83     
84     for(int i = 0; i < m; i++){
85         if(sch[i].addmit.size()){
86             sort(sch[i].addmit.begin(), sch[i].addmit.end(), cmpans);
87             printf("%d", sch[i].addmit[0].id);
88             for(int j = 1; j < sch[i].addmit.size(); j++){
89                 printf(" %d", sch[i].addmit[j].id);
90             }    
91         }
92         printf("
");
93     }
94     
95     
96     return 0;    
97 }