天梯赛使用 OMS 监考系统,需要将参赛队员安排到系统中的虚拟赛场里,并为每个赛场分配一位监考老师。每位监考老师需要联系自己赛场内队员对应的教练们,以便发放比赛账号。为了尽可能减少教练和监考的沟通负担,我们要求赛场的安排满足以下条件:
- 每位监考老师负责的赛场里,队员人数不得超过赛场规定容量 C;
- 每位教练需要联系的监考人数尽可能少 —— 这里假设每所参赛学校只有一位负责联系的教练,且每个赛场的监考老师都不相同。
为此我们设计了多轮次排座算法,按照尚未安排赛场的队员人数从大到小的顺序,每一轮对当前未安排的人数最多的学校进行处理。记当前待处理的学校未安排人数为 n:
- 如果 n≥C,则新开一个赛场,将 C 位队员安排进去。剩下的人继续按人数规模排队,等待下一轮处理;
- 如果 n
- 如果 n
由于近年来天梯赛的参赛人数快速增长,2023年超过了 480 所学校 1.6 万人,所以我们必须写个程序来处理赛场安排问题。
输入格式:
输入第一行给出两个正整数 N 和 C,分别为参赛学校数量和每个赛场的规定容量,其中 0
输出格式:
按照输入的顺序,对每一所参赛高校,在一行中输出学校缩写和该校需要联系的监考人数,其间以 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
- using namespace std;
- #define endl '\n'
- typedef long long ll;
- typedef unsigned long long ull;
- const int maxn = 3e5 + 10;
- const int INF = 0x3fffffff;
- const int mod = 1000000007;
- priority_queue<int> q; // 大根堆
- int n, C;
-
- void solve() {
- cin >> n >> C;
- int ans = 0;
- for (int i = 0; i < n; i++) {
- string sch;
- int cnt;
- cin >> sch >> cnt;
- cout << sch << " " << (cnt + C - 1) / C << endl;
- ans += cnt / C;
- if (cnt % C != 0)
- q.push(cnt % C);
- }
-
- vector<int> vec;
- while (!q.empty()) {
- int t = q.top();
- q.pop();
- bool flag = false;
- for (int i = 0; i < vec.size(); i++) {
- if (C - vec[i] >= t) {
- flag = true;
- vec[i] += t;
- break;
- }
- }
- if (!flag) {
- vec.push_back(t);
- ans++;
- }
- }
- cout << ans;
- }
-
- int main() {
- // freopen("in.txt", "r", stdin);
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- cout << fixed;
- cout.precision(18);
-
- solve();
- return 0;
- }