A25065. 赛场安排
填空题
困难
知识点
题目描述
赛场安排
题目描述
比赛使用 OMS 监考系统，需要将参赛队员安排到系统中的虚拟赛场里，并为每个赛场分配一位监考老师。每位监考老师需要联系自己赛场内队员对应的教练们，以便发放比赛账号。为了尽可能减少教练和监考的沟通负担，我们要求赛场的安排满足以下条件：
- 每位监考老师负责的赛场里，队员人数不得超过赛场规定容量 C；
- 每位教练需要联系的监考人数尽可能少 —— 这里假设每所参赛学校只有一位负责联系的教练，且每个赛场的监考老师都不相同，为此我们设计了多轮次排座算法，按照尚未安排赛场的队员人数从大到小的顺序，每一轮对当前未安排的人数最多的学校进行处理。记当前待处理的学校未安排人数为 n；
- 如果 n ≥ C，则将其中 C 人安排到当前为空的编号最小的赛场，剩下的人继续按人数规模排队，等待下一轮处理；
- 如果 n < C，则寻找剩余空位数大于等于 n 的编号最小的赛场，将队员安排进去；
- 如果 n < C，且找不到任何非空的、剩余空位数大于等于 n 的赛场了，则新开一个赛场，将队员安排进去。
由于近年来参赛人数快速增长，2023年超过了 410 所学校 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参考答案
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <cctype>
#include <string>
using namespace std;
struct School {
string name;
int total;
int remaining;
int supervisors;
School(string n, int t) : name(n), total(t), remaining(t), supervisors(0) {}
};
int main() {
int N, C;
cin >> N >> C;
vector<School> schools;
for (int i = 0; i < N; i++) {
string name;
int num;
cin >> name >> num;
schools.push_back(School(name, num));
}
auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
if (a.first != b.first)
return a.first < b.first;
else
return a.second > b.second;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
for (int i = 0; i < schools.size(); i++) {
pq.push({schools[i].remaining, i});
}
int totalRooms = 0;
vector<set<int>> buckets(51);
while (!pq.empty()) {
int remaining = pq.top().first;
int idx = pq.top().second;
pq.pop();
if (remaining > schools[idx].remaining) {
continue;
}
if (remaining >= C) {
totalRooms++;
schools[idx].supervisors++;
schools[idx].remaining -= C;
if (schools[idx].remaining > 0) {
pq.push({schools[idx].remaining, idx});
}
} else {
bool found = false;
for (int r = remaining; r <= 50; r++) {
if (!buckets[r].empty()) {
found = true;
int room_id = *buckets[r].begin();
buckets[r].erase(room_id);
int new_r = r - remaining;
if (new_r > 0) {
buckets[new_r].insert(room_id);
}
schools[idx].supervisors++;
break;
}
}
if (!found) {
totalRooms++;
schools[idx].supervisors++;
int new_r = C - remaining;
if (new_r > 0) {
buckets[new_r].insert(totalRooms - 1);
}
}
}
}
for (int i = 0; i < N; i++) {
cout << schools[i].name << " " << schools[i].supervisors << endl;
}
cout << totalRooms << endl;
return 0;
}
上一题
下一题