PAT 1080

题目 ： Graduate Admission

分值 ： 30
难度 ： 中等题
思路 ： 结构体排序,按照rank来选择录取学校.
坑点 ： 倒数第二个测试点如果用 cin cout 会超时,改成 scanf 就好了

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std ;
vector <int>::iterator iter ;
set<int>::iterator iter1 ;

int sum [101] ;
typedef struct student
{
    int GE , GI;
    int rank ;
    int self ;
    vector<int > query;
}Students;
typedef struct school
{
    set<int> luqu ;
    int low_rank ;
}School;
School schools[101];
Students data[40001];
bool cmp(student a , student b)
{
    if(a.GE+a.GI != b.GE + b.GI)
        return a.GE+a.GI > b.GE + b.GI ;
    return a.GE > b.GE ;
}
int main() {
    int N ,M ,K ;
    cin >> N >> M >>K;
    for(int i = 0 ; i< M ; i++)
        scanf("%d",&sum[i]);
    for(int i = 0 ; i< N ; i++)
    {
        scanf("%d %d",&data[i].GE ,&data[i].GI) ;
        data[i].self = i ;
        int temp ;
        for(int j = 0 ; j< K ; j++)
        {
            scanf("%d", &temp) ;
            data[i].query.push_back(temp) ;
        }
    }
    sort(data,data+N ,cmp) ;
    for(int i = 0 ; i< N ; i++)   //处理N个 申请
    {
        if(i==0)
        {
            data[i].rank = 1 ;
        }
        else
        {
            if(data[i].GE==data[i-1].GE && data[i].GI ==data[i-1].GI)
                data[i].rank = data[i-1].rank ;
            else data[i].rank = i+1 ;
        }
        bool flag =false ;
        for(iter = data[i].query.begin() ; iter != data[i].query.end() ; iter ++)  //依次看申请的学校
        {
            int Query = *iter ;
            if(schools[Query].luqu.size() < sum[Query] )    //如果申请的学校没满
            {
                schools[Query].luqu.insert(data[i].self);  //被录取
                schools[Query].low_rank = data[i].rank ;    //最低 rank 更新
                break ;                                     //被录取这个学生就跳过了
            }
            else if(schools[Query].luqu.size() >= sum[Query] )  //人满了 但是 你和最后一名分数一样
            {
                if(data[i].rank ==schools[Query].low_rank)
                {
                    schools[Query].luqu.insert(data[i].self);  //被录取
                    break ;                                 //被录取这个学生就跳过了
                }
            }
        }
    }
    for(int i = 0 ;i< M ; i++)
    {
        if(!schools[i].luqu.size()) ;
        else
        {
            for(iter1 = schools[i].luqu.begin() ;iter1 != schools[i].luqu.end() ;iter1++)
            {
                if(iter1!=schools[i].luqu.begin())
                    cout <<" ";
                cout << *iter1 ;
            }
        }
        cout <<endl ;
    }
}