L2-046 天梯赛的赛场安排-PAT团体程序设计天梯赛GPLT

天梯赛使用 OMS 监考系统，需要将参赛队员安排到系统中的虚拟赛场里，并为每个赛场分配一位监考老师。每位监考老师需要联系自己赛场内队员对应的教练们，以便发放比赛账号。为了尽可能减少教练和监考的沟通负担，我们要求赛场的安排满足以下条件：

每位监考老师负责的赛场里，队员人数不得超过赛场规定容量 C；
每位教练需要联系的监考人数尽可能少 —— 这里假设每所参赛学校只有一位负责联系的教练，且每个赛场的监考老师都不相同。

为此我们设计了多轮次排座算法，按照尚未安排赛场的队员人数从大到小的顺序，每一轮对当前未安排的人数最多的学校进行处理。记当前待处理的学校未安排人数为 n：

如果 n≥C，则新开一个赛场，将 C 位队员安排进去。剩下的人继续按人数规模排队，等待下一轮处理；
如果 n<C，则寻找剩余空位数大于等于 n 的编号最小的赛场，将队员安排进去；
如果 n<C，且找不到任何非空的、剩余空位数大于等于 n 的赛场了，则新开一个赛场，将队员安排进去。

由于近年来天梯赛的参赛人数快速增长，2023年超过了 480 所学校 1.6 万人，所以我们必须写个程序来处理赛场安排问题。

输入格式：

输入第一行给出两个正整数 N 和 C，分别为参赛学校数量和每个赛场的规定容量，其中 0<N≤5000，10≤C≤50。随后 N 行，每行给出一个学校的缩写（为长度不超过 6 的非空小写英文字母串）和该校参赛人数（不超过 500 的正整数），其间以空格分隔。题目保证每所学校只有一条记录。

输出格式：

按照输入的顺序，对每一所参赛高校，在一行中输出学校缩写和该校需要联系的监考人数，其间以 1 空格分隔。
最后在一行中输出系统中应该开设多少个赛场。

输入样例：

10 30
zju 30
hdu 93
pku 39
hbu 42
sjtu 21
abdu 10
xjtu 36
nnu 15
hnu 168
hsnu 20

输出样例：

zju 1
hdu 4
pku 2
hbu 2
sjtu 1
abdu 1
xjtu 2
nnu 1
hnu 6
hsnu 1
16

分析：Q中存储待排考场学校的名字和剩余待排人数，人数少的在前面。Uni数组储存第i个学校叫什么名字。room数组存储第i个数组还能坐下多少个人，num表示当前处理的学校还需要几个座位。Num中存储对应学校需要排几个考场。r表示总共需要几个考场，f用来标记现在待排的人能不能插入到现有的空位足够的教室里。
每次去出待排学校里待排人数最少的那一个。如果待排人数大于等于容量C，则需要安排一间全新的考场。如果不等于容量C的话，需要把学校连着剩余待排人数重新插回到优先队列Q里。否则查询所有已有考场是否有哪一间空余作为大于现在待排人数，有的话就在这间考，没有的话就新开一间，并更新一下新考场空余作为数。

#include <iostream>
#include <queue>
#include <map>
#include <string>
using namespace std;
priority_queue<pair<int, string>> Q;
int N, C, t, room[500000], r, num, f;
map<string, int> Num;
vector<string> Uni(5005);
int main() {
    cin >> N >> C;
    for (int i = 1; i <= N; i++) {
        cin >> Uni[i] >> t;
        Q.push({t, Uni[i]});
    }
    while(Q.size()) {
        string SN = Q.top().second;
        num = Q.top().first;
        Q.pop();
        Num[SN]++;
        if (num >= C) {
            room[++r] = 0;
            if(num != C) Q.push({num - C, SN});
        } else {
            f = 0;
            for (int i = 1; i <= r; i++) {
                if (room[i] >= num) {
                    room[i] -= num;
                    f = 1;
                    break;
                }
            }
            if (!f) {
                room[++r] = C - num;
            }
        }
    }
    for (int i = 1; i <= N; i++) cout << Uni[i] << ' ' << Num[Uni[i]] << '\n';
    cout << r;
    return 0;
}

#include <iostream>

#include <queue>

#include <map>

#include <string>

using namespace std;

priority_queue<pair<int, string>> Q;

int N, C, t, room[500000], r, num, f;

map<string, int> Num;

vector<string> Uni(5005);

int main() {

cin >> N >> C;

for (int i = 1; i <= N; i++) {

cin >> Uni[i] >> t;

Q.push({t, Uni[i]});

}

while(Q.size()) {

string SN = Q.top().second;

num = Q.top().first;

Q.pop();

Num[SN]++;

if (num >= C) {

room[++r] = 0;

if(num != C) Q.push({num - C, SN});

} else {

f = 0;

for (int i = 1; i <= r; i++) {

if (room[i] >= num) {

room[i] -= num;

f = 1;

break;

}

if (!f) {

room[++r] = C - num;

}

for (int i = 1; i <= N; i++) cout << Uni[i] << ' ' << Num[Uni[i]] << '\n';

cout << r;

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版