题目描述

据说，2011 年，浙江省约有 100 所研究生院准备着手处理 40,000 多份入学申请。

如果你可以编写一个程序来自动执行录取流程，那将会很有帮助。

每个申请人都必须提供两个成绩：全国入学考试成绩 GE 和面试成绩 GI，申请人的最终成绩是 (GE+GI)/2。

录取规则如下：

• 申请者将根据其最终成绩由高到低进行排名，并且将从排名列表的顶部开始逐一录取。
• 如果申请者的最终成绩并列，则按照 GE 成绩由高到低进行排名，如果成绩仍然并列，则并列者的排名必须相同。
• 每个申请人可以填报 K 个志愿，并且将根据他/她的志愿进行录取：如果按照排名列表，轮到某位学生被录取了，并且其第一志愿学校还未招满人，则他成功被该学校录取。如果名额已满，则按顺序考虑其他志愿，直至成功被录取为止。如果所有报名学校都无法录取该名学生，则该名学生录取失败。
• 如果出现并列排名，并且并列申请人正在申请同一所学校，那么该学校不得只录取其中一部分申请人，即使超过招生限额，也必须全部录取。

输入格式

第一行包含三个整数，N 表示总申请人数量，M 表示学校数量，K 表示可填报志愿数量。

第二行包含 M 个整数，表示每所学校的计划招生人数。

接下来 N 行，每行包含 2+K 个整数，前两个整数表示一名申请人的 GE 和 GI，接下来 K 个整数，表示该申请人的志愿学校编号。

所有学校编号 0∼M−1，所有申请人编号 0∼N−1。

输出格式

输出所有研究生院的录取结果。

每所学校的录取结果占据一行，其中包含所有学校录取的申请人的编号。编号必须按升序排列，并用空格分隔。

每行的末尾必须没有多余的空格。

如果某学校没有录取任何学生，则必须相应地输出空白行。

数据范围

1≤N≤40000,
1≤M≤100,
1≤K≤5,
0≤GE,GI≤100,

每所学校的计划招生人数不会超过2000。

样例

输入样例：

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

输出样例：

0 10
3
5 6 7
2 8

1 4

算法

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 40010, MAXM = 110;

struct Student
{
    int id;
    double ge, gi;
    double sg;
    int want[5];
} stu[MAXN];

struct School
{
    int id;
    int want_num;
    int admission[MAXN];
    int count = 0;
    double last_sg, last_ge;
} sch[MAXM];

bool cmp1(Student a, Student b)
{
    if (a.sg != b.sg) return a.sg > b.sg;
    else return a.ge > b.ge;
}

bool cmp2(int id1, int id2)
{
    return id1 < id2;
}

int main()
{
    int N, M, K;
    cin >> N >> M >> K;

    for (int i = 0; i < M; i ++)
    {
        cin >> sch[i].want_num;
        sch[i].id = i;
    }

    for (int i = 0; i < N; i ++)
    {
        stu[i].id = i;
        scanf("%lf%lf", &stu[i].ge, &stu[i].gi);
        stu[i].sg = (stu[i].ge + stu[i].gi) / 2;
        for (int j = 0; j < K; j ++)
        {
            scanf("%d", &stu[i].want[j]);
        }
    }

    sort(stu, stu + N, cmp1);

    for (int i = 0; i < N; i ++)
    {
        for (int j = 0; j < K; j ++)
        {
            int want_sch = stu[i].want[j];
            if (sch[want_sch].count < sch[want_sch].want_num || (sch[want_sch].last_sg == stu[i].sg && sch[want_sch].last_ge == stu[i].ge))
            {
                sch[want_sch].admission[sch[want_sch].count ++] = stu[i].id;
                sch[want_sch].last_sg = stu[i].sg, sch[want_sch].last_ge = stu[i].ge;
                break;
            }
        }
    }

    for (int i = 0; i < M; i ++)
    {
        sort(sch[i].admission, sch[i].admission + sch[i].count, cmp2);
    }

    for (int i = 0; i < M; i ++)
    {
        for (int j = 0; j < sch[i].count ; j ++)
        {
            printf("%d", sch[i].admission[j]);
            if (j != sch[i].count - 1) printf(" ");
        }
        printf("\n");
    }

    return 0;
}